Rotate Array

Question: Given an array, rotate the array to the right by k steps, where k is non-negative.

You may view the full question here.

Approach 1: Let’s start with a simple approach using a temporary copy of the array. Diving straight to the code —

//Approach 1:
//Runtime: 1ms
//Memory usage: 38.2MB
class Solution {
    public void rotate(int[] nums, int k) {
        int[] copy = new int[nums.length];
        for(int i = 0; i<nums.length; i++){
            copy[i] = nums[i];
        }
        
        for(int i = 0; i<nums.length; i++){
            nums[(i+k)%nums.length] = copy[i];
        }
    }
}

Approach 2.1: Now, let’s try a solution where we rotate the array in-place.

You could check out the solution posted here. (NOTE: You may have to unlock the solution by posting a valid solution first though.)

The core logic used in this approach is that we use one temporary variable and perform in-place swap(swap may be the wrong word to use, as we are ‘rotating’ here). If we proceed to follow this approach we would see that there could be a point when we arrive back to the index where we started; while we might still have more elements in the array yet to be rotated.

Consider the following example —

The in-place rotation starting from index = 0 would look like this —

As we see, the rotation leads us back to our original starting point. If we continue, it would simply be an endless loop. So, we need to keep track of where we started and break out of the loop when we come back to the original starting point. And then, we move to the next index, in our case, index = 0+1 = 1 and we repeat the same process until we cover all the elements. We can probably keep track of that by keeping count of how many elements we have moved so far using a counter.

And the code would look like —

//Approach 2.1:
//Runtime: 1ms
//Memory usage: 37MB
class Solution {
    public void rotate(int[] nums, int k) {
        int start = -1;
        int nextIndex;
        int i;
        int temp;
        int prev = (nums.length>0? nums[0] : 0);
        k=k%nums.length;
        for(int count = 0; count<nums.length && k>0; ){
            start++;
            i = start;
            prev = nums[i];
            do {
                //compute next index
                nextIndex = (i + k) % nums.length;
                //make a copy of the data that will be lost while swapping
                temp = nums[nextIndex];
                //swap
                nums[nextIndex] = prev;
                //prepare for next swap
                prev = temp;
                i = nextIndex;
                //increment count
                count++;
            } while(i!=start && count<nums.length);
        }
    }
}

Approach 2.2: After tweaking the previous approach a bit, by adjusting the variables used for computation. Looks like using new variables in each loop instead of trying to re-use/re-initializing the same speeds up the process. Check out the code below —

//Approach 2.2:
//Runtime: 0ms
//Memory usage: 36.7MB
class Solution {
    public void rotate(int[] nums, int k) {
        k=k%nums.length;
        for(int start = 0, count = 0; count<nums.length && k>0; start++){
            int i = start;
            int prev = nums[i];
            do {
                //compute next index
                int nextIndex = (i + k) % nums.length;
                //make a copy of the data that will be lost while swapping
                int temp = nums[nextIndex];
                //swap
                nums[nextIndex] = prev;
                //prepare for next swap
                prev = temp;
                i = nextIndex;
                //increment count
                count++;
            } while(i!=start && count<nums.length);
        }
    }
}

Find more posts here.

Cheers & Chao!