Java - Rotating array

So the goal is to rotate the elements in an array right a times. As an example; if a==2, then array = {0,1,2,3,4} would become array = {3,4,0,1,2}

Here's what I have:

for (int x = 0; x <= array.length-1; x++){
    array[x+a] = array[x];
}

However, this fails to account for when [x+a] is greater than the length of the array. I read that I should store the ones that are greater in a different Array but seeing as a is variable I'm not sure that's the best solution. Thanks in advance.


Solution 1:

Add a modulo array length to your code:

// create a newArray before of the same size as array

// copy
for(int x = 0; x <= array.length-1; x++){
  newArray[(x+a) % array.length ] = array[x];
}

You should also create a new Array to copy to, so you do not overwrite values, that you'll need later on.

Solution 2:

In case you don't want to reinvent the wheel (maybe it's an exercise but it can be good to know), you can use Collections.rotate.

Be aware that it requires an array of objects, not primitive data type (otherwise you'll swap arrays themselves in the list).

Integer[] arr = {0,1,2,3,4};
Collections.rotate(Arrays.asList(arr), 2);
System.out.println(Arrays.toString(arr)); //[3, 4, 0, 1, 2]

Solution 3:

Arraycopy is an expensive operation, both time and memory wise. Following would be an efficient way to rotate array without using extra space (unlike the accepted answer where a new array is created of the same size).

public void rotate(int[] nums, int k) { // k = 2
    k %= nums.length;
    // {0,1,2,3,4}

    reverse(nums, 0, nums.length - 1); // Reverse the whole Array
    // {4,3,2,1,0}

    reverse(nums, 0, k - 1); // Reverse first part (4,3 -> 3,4)
    // {3,4,2,1,0}

    reverse(nums, k, nums.length - 1); //Reverse second part (2,1,0 -> 0,1,2)
    // {3,4,0,1,2}
}

public void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}