Rotate Array
MedPrompt
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:
- Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
- Could you do it in-place with
O(1)extra space?
Approaches
4 approaches with complexity analysis and trade-offs.
This approach simulates the rotation process step by step. For each of the k rotation steps, it moves every element in the array one position to the right. The last element is moved to the first position.
Algorithm
-
- Calculate the effective rotation count by taking
k = k % nums.length.
- Calculate the effective rotation count by taking
-
- Repeat the rotation process
ktimes.
- Repeat the rotation process
-
- In each of the
kiterations, perform a single right rotation:
- a. Store the last element of the array in a temporary variable,
last = nums[n-1]. - b. Shift all elements from index
n-2down to0one position to the right. This can be done by iterating fromj = n-1down to1and settingnums[j] = nums[j-1]. - c. Place the stored
lastelement at the beginning of the array:nums[0] = last.
- In each of the
Walkthrough
The most straightforward way to solve the problem is to literally rotate the array k times. A single right rotation involves taking the last element and moving it to the front, while shifting every other element one position to the right.
We can implement this by running a loop k times. Inside this loop, we perform the single rotation. To avoid unnecessary rotations when k is larger than the array length n, we first take k = k % n.
class Solution { public void rotate(int[] nums, int k) { int n = nums.length; // To handle cases where k > n k %= n; for (int i = 0; i < k; i++) { int lastElement = nums[n - 1]; // Shift all elements one position to the right for (int j = n - 1; j > 0; j--) { nums[j] = nums[j - 1]; } // Place the last element at the front nums[0] = lastElement; } }}Complexity
Time
O(n * k)
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
It's an in-place solution, using constant extra space.
Cons
Extremely inefficient for large arrays or large values of
k.Will likely result in a 'Time Limit Exceeded' (TLE) error on most coding platforms for larger constraints.
This approach uses an auxiliary array to store the rotated elements. Each element nums[i] is placed at its new position (i + k) % n in the new array. Finally, the new array is copied back to the original array.
Algorithm
-
- Create a new array
resultof the same size asnums.
- Create a new array
-
- Iterate through the original
numsarray from indexi = 0ton-1.
- Iterate through the original
-
- For each element
nums[i], calculate its new position in the rotated array, which is(i + k) % n.
- For each element
-
- Place the element
nums[i]into theresultarray at the calculated new position:result[(i + k) % n] = nums[i].
- Place the element
-
- After iterating through all elements, copy the contents of the
resultarray back into the originalnumsarray.
- After iterating through all elements, copy the contents of the
Walkthrough
A more efficient approach in terms of time complexity is to use an extra array. We can determine the final position of each element and place it there directly in a new array. An element currently at index i will be at index (i + k) % n after the rotation, where n is the length of the array.
We can create a new array of the same size, iterate through the original array, and place each element in its correct final position in the new array. Once the new array is fully populated, we copy it back to the original array.
class Solution { public void rotate(int[] nums, int k) { int n = nums.length; int[] result = new int[n]; for (int i = 0; i < n; i++) { result[(i + k) % n] = nums[i]; } // Copy the result back to the original array System.arraycopy(result, 0, nums, 0, n); }}Complexity
Time
O(n)
Space
O(n)
Trade-offs
Pros
Time complexity is linear, which is a significant improvement over the brute-force method.
The logic is straightforward and easy to implement correctly.
Cons
Requires extra space proportional to the size of the input array.
Fails the follow-up requirement of solving it in-place with O(1) extra space.
This is an in-place approach that moves elements to their correct positions in cycles. It iterates through the array, and for each element, it follows the cycle of replacements until every element is in its final place. The number of cycles is determined by the greatest common divisor (GCD) of the array length n and the rotation amount k.
Algorithm
-
- Reduce
kby takingk = k % n. Ifkis 0, no rotation is needed.
- Reduce
-
- Initialize a counter
countfor the number of elements placed in their correct positions to 0.
- Initialize a counter
-
- Loop with a
startindex from0ton-1. This loop will effectively rungcd(n, k)times because the inner loop places multiple elements.
- Loop with a
-
- For each
start, begin a cycle. Letcurrent = startand store the valuenums[start]in a temporary variableprev.
- For each
-
- Use a
do-whileloop to traverse the cycle:
- a. Calculate the
nextindex:next = (current + k) % n. - b. Swap the value at
nums[next]withprev.int temp = nums[next]; nums[next] = prev; prev = temp; - c. Move to the next position in the cycle:
current = next. - d. Increment the
countof placed elements.
- Use a
-
- The
do-whileloop terminates when the cycle is complete (i.e.,current == start).
- The
-
- The outer loop continues until all elements are placed (
count == n).
- The outer loop continues until all elements are placed (
Walkthrough
This is an advanced in-place algorithm that achieves optimal time and space complexity. The core idea is that the rotation permutes elements in disjoint cycles. An element at index i moves to (i+k)%n, the element there moves to (i+2k)%n, and so on, until we return to i.
We can process one cycle at a time. We start at an index, say 0, and move the element to a temporary variable. Then we move the element from its destination to index 0. We continue this process until the cycle is complete. If n and k are not coprime, there will be multiple cycles. The number of cycles is gcd(n, k). We need to start a new process for each cycle.
class Solution { public void rotate(int[] nums, int k) { int n = nums.length; k = k % n; if (k == 0) { return; } int count = 0; // Number of elements placed for (int start = 0; count < n; start++) { int current = start; int prevValue = nums[start]; do { int nextIdx = (current + k) % n; int temp = nums[nextIdx]; nums[nextIdx] = prevValue; prevValue = temp; current = nextIdx; count++; } while (start != current); } }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Optimal time complexity of O(n).
Optimal space complexity of O(1) as it's an in-place algorithm.
Cons
The implementation is more complex and less intuitive than other optimal solutions.
The memory access pattern is non-sequential (jumping by
ksteps), which can be less cache-friendly than sequential access.
This is an elegant and efficient in-place solution. The algorithm consists of three steps: first, reverse the entire array. Second, reverse the first k elements. Third, reverse the remaining n-k elements. This sequence of reversals correctly places all elements in their rotated positions.
Algorithm
-
- Define a helper function
reverse(nums, start, end)that reverses the sub-array ofnumsfrom thestartindex to theendindex.
- Define a helper function
-
- In the main
rotatefunction, first handle the case wherekis larger than the array length by takingk = k % nums.length.
- In the main
-
- Reverse the entire array. Call
reverse(nums, 0, n - 1).
- Reverse the entire array. Call
-
- Reverse the first
kelements of the now-reversed array. Callreverse(nums, 0, k - 1).
- Reverse the first
-
- Reverse the remaining
n-kelements. Callreverse(nums, k, n - 1).
- Reverse the remaining
Walkthrough
This is a very clever in-place solution with O(n) time complexity. The idea is that a right rotation by k moves the last k elements to the front and the first n-k elements to the back.
Let's take nums = [1,2,3,4,5,6,7] and k = 3. The goal is [5,6,7,1,2,3,4].
- Reverse the entire array: The original array
[1,2,3,4,5,6,7]becomes[7,6,5,4,3,2,1]. - Reverse the first
kelements: The firstk=3elements are[7,6,5]. Reversing them gives[5,6,7]. The array is now[5,6,7,4,3,2,1]. - Reverse the remaining
n-kelements: The rest of the elements are[4,3,2,1]. Reversing them gives[1,2,3,4]. The array is now[5,6,7,1,2,3,4], which is the correct result.
This three-step reversal process works for any n and k.
class Solution { public void rotate(int[] nums, int k) { int n = nums.length; k %= n; // Step 1: Reverse the entire array reverse(nums, 0, n - 1); // Step 2: Reverse the first k elements reverse(nums, 0, k - 1); // Step 3: Reverse the remaining n-k elements reverse(nums, k, n - 1); } private void reverse(int[] nums, int start, int end) { while (start < end) { int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; start++; end--; } }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Optimal time complexity of O(n).
Optimal space complexity of O(1) as it's an in-place algorithm.
The code is clean, concise, and generally easier to implement correctly than the cyclic replacement method.
Memory access is sequential during reversals, which is cache-friendly.
Cons
The underlying logic might not be immediately obvious without working through an example.
Solutions
Solution
public class Solution { private int[] nums; public void Rotate(int[] nums, int k) { this.nums = nums; int n = nums.Length; k %= n; reverse(0, n - 1); reverse(0, k - 1); reverse(k, n - 1); } private void reverse(int i, int j) { for (; i < j; ++i, --j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } }}class Solution { private int [] nums ; public void rotate ( int [] nums , int k ) { this . nums = nums ; int n = nums . length ; k %= n ; reverse ( 0 , n - 1 ); reverse ( 0 , k - 1 ); reverse ( k , n - 1 ); } private void reverse ( int i , int j ) { for (; i < j ; ++ i , -- j ) { int t = nums [ i ]; nums [ i ] = nums [ j ]; nums [ j ] = t ; } } }/** * @param {number[]} nums * @param {number} k * @return {void} Do not return anything, modify nums in-place instead. */ var rotate = function (nums, k) { const n = nums.length; k %= n; const reverse = (i, j) => { for (; i < j; ++i, --j) { [nums[i], nums[j]] = [nums[j], nums[i]]; } }; reverse(0, n - 1); reverse(0, k - 1); reverse(k, n - 1); };class Solution { public: void rotate ( vector < int >& nums , int k ) { int n = nums . size (); k %= n ; reverse ( nums . begin (), nums . end ()); reverse ( nums . begin (), nums . begin () + k ); reverse ( nums . begin () + k , nums . end ()); } };class Solution : def rotate ( self , nums : List [ int ], k : int ) -> None : k %= len ( nums ) nums [:] = nums [ - k :] + nums [: - k ] ############ class Solution : def rotate ( self , nums : List [ int ], k : int ) -> None : """ Do not return anything, modify nums in-place instead. """ n = len ( nums ) k %= n if n < 2 or k == 0 : return nums [:] = nums [:: - 1 ] nums [: k ] = nums [: k ][:: - 1 ] nums [ k :] = nums [ k :][:: - 1 ] ############ class Solution ( object ): def rotate ( self , nums , k ): """ :type nums: List[int] :type k: int :rtype: void Do not return anything, modify nums in-place instead. """ if len ( nums ) == 0 or k == 0 : return def reverse ( start , end , s ): while start < end : s [ start ], s [ end ] = s [ end ], s [ start ] start += 1 end -= 1 n = len ( nums ) - 1 k = k % len ( nums ) reverse ( 0 , n - k , nums ) reverse ( n - k + 1 , n , nums ) reverse ( 0 , n , nums )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.