Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [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 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]
Constraints:
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 10 <= k <= 105
Follow up:
O(1) extra space?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.
This approach involves using an additional array to store the rotated order of elements. We calculate the new position for each element and place it in the new array. Finally, copy the elements of this new temporary array back into the original array.
This C solution creates a temporary array of the same size as the input. It calculates the new index for each element using modulo arithmetic to ensure cyclic behavior, then it fills this temporary array and finally copies it back into the original array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the number of elements in the array. Space Complexity: O(n) due to the use of an additional array for rotation.
This approach involves reversing parts of the array to achieve the rotation without additional space. First, reverse the whole array, then reverse the first k elements, and finally reverse the remaining n-k elements. This series of reversals effectively performs the rotation in-place without needing extra storage.
This C solution performs in-place array reordering by reversing the entire array, the first k elements, and the last n-k elements. This avoids the need for auxiliary space while achieving the desired rotation result.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n). Space Complexity: O(1) as it does not require additional arrays.
| Approach | Complexity |
|---|---|
| Using Additional Array | Time Complexity: O(n) where n is the number of elements in the array. Space Complexity: O(n) due to the use of an additional array for rotation. |
| In-Place Reversal | Time Complexity: O(n). Space Complexity: O(1) as it does not require additional arrays. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Additional Array | O(n) | O(n) | When clarity matters more than memory usage. Good for quickly explaining the index mapping logic. |
| In-Place Reversal | O(n) | O(1) | Preferred interview solution when memory is constrained and in-place array manipulation is expected. |
Rotate Array by K places | Union, Intersection of Sorted Arrays | Move Zeros to End | Arrays Part-2 • take U forward • 1,241,837 views views
Watch 9 more video solutions →Practice Rotate Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor