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 <= 105Follow up:
O(1) extra space?The Rotate Array problem asks you to shift elements of an array to the right by k steps. A straightforward way to think about it is by using an extra array where each element is placed at its new index using modular arithmetic. While simple, this requires additional memory.
A more optimal technique uses the array reversal strategy. The idea is to reverse the entire array first, then reverse the first k elements, and finally reverse the remaining n - k elements. This cleverly rearranges the positions so that elements appear rotated without needing extra space.
Another conceptual approach is cyclic replacements, where elements are moved along calculated cycles until all indices are visited. This method relies on modular index movement.
The reversal method is typically preferred in interviews because it achieves O(n) time complexity with O(1) extra space while keeping the implementation relatively clean.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Extra Array | O(n) | O(n) |
| Array Reversal Technique | O(n) | O(1) |
| Cyclic Replacement | O(n) | O(1) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
The easiest solution would use additional memory and that is perfectly fine.
The actual trick comes when trying to solve this problem without using any additional memory. This means you need to use the original array somehow to move the elements around. Now, we can place each element in its original location and shift all the elements around it to adjust as that would be too costly and most likely will time out on larger input arrays.
One line of thought is based on reversing the array (or parts of it) to obtain the desired result. Think about how reversal might potentially help us out by using an example.
The other line of thought is a tad bit complicated but essentially it builds on the idea of placing each element in its original position while keeping track of the element originally in that position. Basically, at every step, we place an element in its rightful position and keep track of the element already there or the one being overwritten in an additional variable. We can't do this in one linear pass and the idea here is based on <b>cyclic-dependencies</b> between elements.
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.
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.
1#include <iostream>
2#include <vector>
3
4void rotate(std::vector<int>& nums, int k) {
5 int n = nums.size();
6 std::vector<int> rotated(n);
7 k = k % n;
8 for (int i = 0; i < n; ++i) {
9 rotated[(i + k) % n] = nums[i];
10 }
11 nums = rotated;
12}
13
14int main() {
15 std::vector<int> nums = {1,2,3,4,5,6,7};
16 int k = 3;
17 rotate(nums, k);
18 for(int num : nums) {
19 std::cout << num << " ";
20 }
21 return 0;
22}This C++ solution follows similar logic as the C example using a temporary vector to store the rotated results and copying back to the original vector.
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.
Time Complexity: O(n). Space Complexity: O(1) as it does not require additional arrays.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Rotate Array is a commonly asked interview question at many top tech companies including FAANG. It tests understanding of array manipulation, in-place algorithms, and time-space optimization.
Using k % n ensures the rotation count stays within the array length. Rotating an array n times results in the same array, so reducing k avoids unnecessary operations.
The optimal approach is the array reversal technique. It rotates the array by reversing the entire array and then reversing two sub-parts. This method runs in O(n) time and uses O(1) extra space.
The problem primarily uses arrays along with index manipulation and modular arithmetic. Two-pointer techniques are often used in the reversal approach to swap elements in place.
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.