189: Rotate Array

Given an array and an int k, rotate the array k number of steps to the right. The especial challenge of this problem is to find at least three solutions to it. Fortunately, we’re not required to do it in-place.

1. Rotate the array one step k times.

This is the solution suggested by the description’s examples.

Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]

(The hiccup I had was that the inner loop needs to go backwards through the array, or else it just copies element 2 over and over)

public void rotate(int[] nums, int k) {
        for (int i=0; i<k; i++){
            int saveItem = nums[nums.length-1];
            for (int j=nums.length-1; j>0; j--){
                nums[j] = nums[j-1];
            }
            nums[0] = saveItem;
        }
    }

This works, but I don’t like nested loops. I have a hard time following them, and there’s the time complexity issue – this solution actually failed submission because one of the tests timed out. Instead of rotating the array one spot k times, let’s rotate it k spaces once.

2.

We’re not locked into doing this in place, so let’s add the items to another array, starting at position nums.length-k. I’m feeling lazy, so I’m going to make our temporary array an ArrayList, so that I can just add to it without having to pay attention to what index I’m adding to. But here’s a problem: What if k is larger than the length of num? Well, then we have to take the remainder and use that as k instead.

public void rotate(int[] nums, int k) {
        k%=nums.length;
        ArrayList<Integer> tempArrayList = new ArrayList<Integer>();
        for (int i = nums.length-k; i<nums.length; i++){
            tempArrayList.add(nums[i]);
        }
        for (int i = 0; i<nums.length-k; i++){
            tempArrayList.add(nums[i]);
        }
        Integer[] tempArray = tempArrayList.toArray(new Integer[0]);
        for (int i = 0; i<nums.length; i++){
            nums[i] = tempArray[i];
        }
    }

This still sucks. The time complexity is better because I’ve unnested the loops, but it still performs badly.

3. Break the array in two and reassemble it.

I want to ditch handcoding loops altogether. Let’s make two smaller arrays, store the two parts of nums in them, then reassemble nums by swapping those two parts.

public void rotate(int[] nums, int k) {
        k%=nums.length;
        int[] partOne = Arrays.copyOfRange(nums, 0, nums.length-k);
        int[] partTwo = Arrays.copyOfRange(nums, nums.length-k, nums.length);
        System.arraycopy(partOne, 0, nums, k, partOne.length);
        System.arraycopy(partTwo, 0, nums, 0, k);
    }

This is a chunkier version of the preferred answer. I’m moving array parts as whole pieces, instead of swapping individual items.

4. The preferred solution: reverse – reverse

You can do this by reversing the first chunk of the array, reversing the second chunk of the array, and the reversing the entire thing:

Example:-1234567 ,k=3
1.first reverse the numbers form index 0 to n-k;
->4321 567
2.reverse the k elements from the last
->4321 765
3.now reverse the whole nums;
->5671234

In Java, this looks something like this:

public void rotate(int[] nums, int k) {
    int n = nums.length;
    k %= n;    
    // Reverse the first k elements
    reverse(nums, 0, k - 1);
    
    // Reverse the remaining elements
    reverse(nums, k, n - 1);

    // Reverse the entire array
    reverse(nums, 0, n - 1);
}

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

I did not write this one.

I honestly like my solution 3 better, because it’s less verbose, it is a little easier to visualize why it works, and for Java at least, it doesn’t require writing a secondary function to call.