Rotate Array By K

Problem Link

Rotate Array – LeetCode

Problem: Rotate Array

Problem Statement

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

The rotation should be done in-place, with O(1) extra space if possible.

Examples

Example 1
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:

• Rotate 1 step → [7,1,2,3,4,5,6]

• Rotate 2 steps → [6,7,1,2,3,4,5]

• Rotate 3 steps → [5,6,7,1,2,3,4]

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

• Rotate 1 step → [99,-1,-100,3]

• Rotate 2 steps → [3,99,-1,-100]

Constraints

• 1 <= nums.length <= 10⁵

• -2³¹ <= nums[i] <= 2³¹ - 1

• 0 <= k <= 10⁵

Intuition

A rotation by k steps means every element moves to the right by k places, wrapping around to the front if needed. Instead of moving each element one by one (which is inefficient), we can use reversal to rotate the array in-place efficiently.

Approach

To rotate the array to the right by k steps:

1. Normalize k by doing k %= n (since rotating by n brings the array to the same state).

2. Reverse the first part: nums[0...n-k-1]

3. Reverse the second part: nums[n-k...n-1]

4. Reverse the entire array: nums[0...n-1]

This effectively rotates the array by k steps.

Code (Java)

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        if (k == 0) return;
        reverse(nums, 0, n - k - 1);
        reverse(nums, n - k, n - 1);
        reverse(nums, 0, n - 1);
    }

    public void reverse(int[] nums, int s, int e) {
        while (s < e) {
            nums[s] = nums[s] ^ nums[e];
            nums[e] = nums[s] ^ nums[e];
            nums[s] = nums[s] ^ nums[e];
            s++;
            e--;
        }
    }
}

Note: The reverse function uses the XOR swap technique to swap elements in-place without using a temporary variable.

Time and Space Complexity

• Time Complexity: O(n)
  Each element is visited at most twice during reversal.

• Space Complexity: O(1)
  Reversals are performed in-place with constant space.

Dry Run

Input: nums = [1,2,3,4,5,6,7], k = 3

1. k %= 7 → k = 3

2. Reverse nums[0...3] → Reverse [1,2,3,4] → [4,3,2,1,5,6,7]

3. Reverse nums[4...6] → Reverse [5,6,7] → [4,3,2,1,7,6,5]

4. Reverse the whole array → Reverse [4,3,2,1,7,6,5] → [5,6,7,1,2,3,4]

Output: [5,6,7,1,2,3,4]

Conclusion

This is an optimal in-place solution using the three-reversal technique to rotate the array. It ensures linear time complexity and constant space, fulfilling both efficiency and in-place requirements.