Code Implementation

class Solution:
    def rotate(self, nums, k):
        n = len(nums)
        k = k % n  # In case k > n
        # Helper function to reverse a portion of the list in-place
        def reverse(start, end):
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1
        # Reverse the whole array
        reverse(0, n - 1)
        # Reverse the first k elements
        reverse(0, k - 1)
        # Reverse the rest
        reverse(k, n - 1)

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        // Helper lambda to reverse part of the array
        auto reverse = [&](int start, int end) {
            while (start < end) {
                swap(nums[start], nums[end]);
                start++;
                end--;
            }
        };
        reverse(0, n - 1);
        reverse(0, k - 1);
        reverse(k, n - 1);
    }
};

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

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

Problem Description

You are given an array of integers nums and an integer k. Your task is to rotate the array to the right by k steps, where k is non-negative. This means each element in nums moves to the position (i + k) % n, where n is the length of the array.

• You must perform the rotation in-place (without using extra space for another array).
• All elements must be moved, and no element should be overwritten before it is moved.
• You must provide a solution with O(1) extra space.
• There is only one valid result for each input.

Thought Process

At first glance, it might seem natural to move each element k positions forward in the array. However, directly assigning each element to its new position can cause overwriting of values that have not yet been moved. To avoid this, a brute-force approach could involve using an extra array to copy elements to their correct positions, but this does not meet the in-place constraint.

To solve the problem efficiently and in-place, we need to find a way to rearrange the elements without using extra space or overwriting important values. One clever observation is that rotating the array to the right by k steps is equivalent to:

• Reversing the entire array
• Reversing the first k elements
• Reversing the remaining n-k elements

This sequence of reversals ensures that all elements are moved to their correct positions without any loss of data.

Solution Approach

Let's break down the steps to rotate the array in-place using the reversal method:

1. Normalize k: Since rotating by the array's length brings it back to its original configuration, we use k = k % n to handle cases where k is greater than the array length.
2. Reverse the entire array: This moves all elements to the opposite ends, so the last element becomes the first, the second last becomes the second, and so on.
3. Reverse the first k elements: This puts the elements that will be at the front of the rotated array in the correct order.
4. Reverse the remaining n-k elements: This restores the order of the rest of the array.

We use a helper function to reverse a subarray in-place by swapping elements from both ends moving towards the center. This approach is efficient and requires only a constant amount of extra space.

Example Walkthrough

Let's walk through an example with nums = [1, 2, 3, 4, 5, 6, 7] and k = 3:

1. Normalize k: k = 3 % 7 = 3
2. Reverse the entire array: [7, 6, 5, 4, 3, 2, 1]
3. Reverse the first k elements: Reverse indices 0 to 2: [5, 6, 7, 4, 3, 2, 1]
4. Reverse the remaining n-k elements: Reverse indices 3 to 6: [5, 6, 7, 1, 2, 3, 4]

The final array [5, 6, 7, 1, 2, 3, 4] is the original array rotated to the right by 3 steps.

Time and Space Complexity

• Brute-force approach: Using an extra array and copying elements takes O(n) time and O(n) space, which does not meet the in-place requirement.
• Optimized reversal approach: Each reversal operation is O(n), and we perform three reversals, so the total time complexity is O(n). Since all operations are done in-place, the extra space complexity is O(1).

The reversal method is both time-efficient and space-efficient.

Summary

The key insight for efficiently rotating an array in-place is to use the reversal technique. By reversing the entire array and then reversing its parts, we can achieve the desired rotation without any extra space. This approach is elegant, simple, and adheres to the problem's constraints, making it a popular solution for the Rotate Array problem.