Rotate Array - Video Solutions

Problem Overview: You are given an integer array nums and a number k. Rotate the array to the right by k steps. Each rotation shifts elements right, and the last element wraps around to the front. The main challenge is performing this efficiently for large arrays.

Approach 1: Using Additional Array (O(n) time, O(n) space)

Create a new array of the same size and place every element directly into its final rotated position. The key observation is that an element at index i moves to (i + k) % n after rotation, where n is the array length. First compute k = k % n to avoid unnecessary rotations. Iterate through the original array, compute the target index for each element, and store it in the new array. Finally copy the values back to nums. This approach is easy to reason about and avoids tricky pointer manipulation, but it requires extra memory proportional to the array size.

Approach 2: In-Place Reversal (O(n) time, O(1) space)

This approach performs the rotation without allocating extra memory by using the reverse array technique. First reverse the entire array. Then reverse the first k elements, followed by reversing the remaining n - k elements. These three reversals reposition elements exactly as if the array had been rotated. The method relies on swapping elements from both ends using the two pointers technique. Time complexity stays linear because each element is swapped at most once, and space complexity remains constant.

Both solutions rely on understanding index movement inside an array. The modulo operation from math ensures rotations larger than the array length still produce the correct result.

Recommended for interviews: The in-place reversal method is the expected optimal solution. It runs in O(n) time with O(1) space and demonstrates strong understanding of array manipulation and pointer techniques. The additional-array method is often discussed first because it clearly shows the index mapping logic, but the in-place approach signals deeper algorithmic skill.