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’re given an integer array nums and an integer k. The task is to rotate the array to the right by k steps, meaning each element shifts right and wraps around to the beginning. For example, rotating [1,2,3,4,5,6,7] by 3 results in [5,6,7,1,2,3,4].
This problem tests your understanding of array manipulation and how to perform cyclic shifts efficiently. A key detail: when k is larger than the array length, only k % n rotations matter.
Approach 1: Using Additional Array (O(n) time, O(n) space)
Create a new array of the same size and place each element directly in its rotated position. First compute k = k % n so unnecessary rotations are avoided. Then iterate through the array and place each element at index (i + k) % n in the new array. After the pass finishes, copy the result back to the original array.
This approach works because the modulo operation naturally handles the wrap‑around from the end of the array back to the front. It’s easy to implement and very readable. The tradeoff is extra memory usage since an additional array of size n is required.
Approach 2: In-Place Reversal (O(n) time, O(1) space)
The optimal solution avoids extra memory by reversing sections of the array in place. The key insight: a right rotation can be expressed as three reversals. First reverse the entire array. Then reverse the first k elements. Finally reverse the remaining n - k elements.
Example: [1,2,3,4,5,6,7] with k = 3. Reverse all → [7,6,5,4,3,2,1]. Reverse first 3 → [5,6,7,4,3,2,1]. Reverse the rest → [5,6,7,1,2,3,4]. Each reversal uses two pointers moving from both ends toward the center, a common pattern in two pointers problems.
This method performs a constant number of passes over the array, giving O(n) time complexity and O(1) extra space. The math behind the rotation and modulo operation ties directly to concepts in math and cyclic indexing.
Recommended for interviews: Interviewers typically expect the in-place reversal approach. The additional array solution shows you understand the rotation mapping, but the reversal method demonstrates deeper algorithmic thinking and space optimization. Both run in linear time, but achieving O(1) space is the key differentiator.
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.
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.
Time Complexity: O(n). Space Complexity: O(1) as it does not require additional arrays.
We can assume the length of the array is n and calculate the actual number of steps needed by taking the module of k and n, which is k bmod n.
Next, let us reverse three times to get the final result:
k elements.n - k elements.For example, for the array [1, 2, 3, 4, 5, 6, 7], k = 3, n = 7, k bmod n = 3.
[7, 6, 5, 4, 3, 2, 1].k elements. We get [5, 6, 7, 4, 3, 2, 1].n - k elements. We get [5, 6, 7, 1, 2, 3, 4], which is the final result.The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| 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. |
| Reverse three times | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Additional Array | O(n) | O(n) | Simple implementation and readability matter more than memory usage |
| In-Place Reversal | O(n) | O(1) | Preferred in interviews or memory-constrained environments |
Rotate Array - Leetcode 189 - Python • NeetCode • 248,894 views views
Watch 9 more video solutions →Practice Rotate Array with our built-in code editor and test cases.
Practice on FleetCode