189. Rotate Array - Detailed Explanation

Problem Statement

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. This means that the array’s elements are shifted to the right k times, with elements wrapping around from the end to the beginning.

Examples

1. Input: nums = [1,2,3,4,5,6,7], k = 3
   Output: [5,6,7,1,2,3,4]
   Explanation: Rotate the array right by 3 steps. The last three elements [5,6,7] move to the front.

2. Input: nums = [-1,-100,3,99], k = 2
   Output: [3,99,-1,-100]
   Explanation: Rotate the array right by 2 steps. The last two elements [3,99] move to the front.

Constraints

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

(If k is larger than the array length n, effective rotation is k % n because rotating n times brings the array back to original.)

Hints to Solve the Problem

1. Using Extra Space: Consider making a copy of the array and placing each element in its new rotated position.
2. Using Cyclic Replacement: Try to visualize how elements move in cycles when rotating. You might traverse the array by jumping indices.
3. Using Reverse Technique: A clever trick is to reverse parts of the array to achieve the rotation in-place efficiently.

Approaches to Solve the Problem

Approach 1: Brute Force (Inefficient for Large Inputs)

Idea: Rotate the array one step at a time, repeated k times. In each single-step rotation, take the last element of nums and move it to the front, while shifting all other elements one position to the right. This will eventually rotate the array by k positions, but it performs a lot of unnecessary moves when k is large.

Complexity: Each step rotation is O(n), and doing this k times leads to O(n * k) time complexity , which is very slow when both n and k are large. Space complexity is O(1) (in-place rotation).

Approach 2: Using Extra Space

Idea: Use an additional array to re-arrange elements in one pass. Specifically, create a new array temp of the same length. For each index i in the original array, place nums[i] into temp[(i + k) % n]. This calculation finds the new index for element nums[i] after rotation (using modulo to wrap around). After this, copy the temp array back into nums to reflect the rotation.

Complexity: This method uses a single loop to fill the new array, so the time complexity is O(n). However, it requires extra space of size n for the temporary array (space complexity O(n)). In practice, it’s efficient for time but uses more memory.

Approach 3: Using Reversal (Optimal Solution)

Idea: This optimal in-place solution uses the reversal algorithm. The process is:

1. Reverse the entire array.
2. Reverse the first k elements.
3. Reverse the remaining n - k elements.

Reversing the whole array puts the last k elements in front, but in reverse order. Then reversing the first k restores those k elements to their correct order at the front. Finally, reversing the rest of the array fixes the order of the remaining elements. After these three reversals, the array is rotated to the right by k positions.

Complexity: All operations are done in-place with a few swaps, and each element is moved at most once. The time complexity is O(n) for reversing the segments, and space complexity is O(1) (only a few variables for swapping). This meets the optimal requirements.

Python Code