32. Rotate Array

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. Modify the array in-place.

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation: Rotate right 3 steps: [7,1,2,3,4,5,6] -> [6,7,1,2,3,4,5] -> [5,6,7,1,2,3,4]

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]

Problem Breakdown:

1. First, handle the case where k is larger than the array length by taking k % n. A full rotation returns the array to its original state.

• k = k % len(nums)

2. The trick is to use three reverse operations. First reverse the entire array.

• def reverse(arr, start, end):
      while start < end:
          arr[start], arr[end] = arr[end], arr[start]
          start += 1
          end -= 1

3. Reverse the entire array, then reverse the first k elements, then reverse the remaining elements.

• reverse(nums, 0, len(nums) - 1)  # Reverse all
  reverse(nums, 0, k - 1)           # Reverse first k
  reverse(nums, k, len(nums) - 1)   # Reverse rest

Summary:

Use the three-reverse trick: reverse the whole array, then reverse the first k elements, then reverse the rest. This achieves an in-place rotation in O(n) time with O(1) space.

Time and Space Complexity:

Time Complexity: O(n) - each element is visited a constant number of times.

Space Complexity: O(1) - rotation is done in-place.

Python Solution:

def rotate(nums, k):
    def reverse(start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1
    k = k % len(nums)
    reverse(0, len(nums) - 1)
    reverse(0, k - 1)
    reverse(k, len(nums) - 1)

JavaScript Solution:

var rotate = function(nums, k) {
    k = k % nums.length;
    const reverse = (start, end) => {
        while (start < end) {
            [nums[start], nums[end]] = [nums[end], nums[start]];
            start++;
            end--;
        }
    };
    reverse(0, nums.length - 1);
    reverse(0, k - 1);
    reverse(k, nums.length - 1);
};

Java Solution:

class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 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--;
        }
    }
}