LeetCode · #189
Rotate Array Solution
Rotate the array to the right by k steps, in-place if possible.
01
Section One · Problem
Problem Statement
Given an integer array nums, rotate it to the right by k steps.
Example
Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4]
02
Section Two · Approach 1
Extra Array — O(n) space
Place each element into its rotated position in a temp array: temp[(i + k) % n] = nums[i], then copy back.
Why we can do better: This uses O(n) extra space. We can do it in-place using three reversals.
03
Section Three · Approach 2
Three Reversals — O(1) space
Normalize k with k %= n. Then:
1) Reverse whole array
2) Reverse first k elements
3) Reverse remaining n-k elements
Why this works:
- A right rotation splits array into tail and head.
- Reversing all flips order, and the two sub-reversals restore internal order of each part.
04
Section Four · Trace
Visual Walkthrough
For [1,2,3,4,5,6,7], k=3:
Reverse all → [7,6,5,4,3,2,1]
Reverse first 3 → [5,6,7,4,3,2,1]
Reverse rest → [5,6,7,1,2,3,4]
05
Section Five · Implementation
Code — Java & Python
Java — In-place reversals
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
rev(nums, 0, n - 1);
rev(nums, 0, k - 1);
rev(nums, k, n - 1);
}
private void rev(int[] a, int l, int r) {
while (l < r) {
int t = a[l];
a[l++] = a[r];
a[r--] = t;
}
}
}
Python — In-place reversals
class Solution:
def rotate(self, nums: list[int], k: int) -> None:
n = len(nums)
k %= n
def rev(l: int, r: int) -> None:
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
rev(0, n - 1)
rev(0, k - 1)
rev(k, n - 1)
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space |
|---|---|---|
| Extra array | O(n) | O(n) |
| Three reversals | O(n) | O(1) |
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | Input | Expected |
|---|---|---|
| k > n | n=7, k=10 | Use k%=n (10→3) |
| k = 0 | [1,2,3], k=0 | No change |
| n = 1 | [5], k=99 | No change |
Common mistake: forgetting
k %= n. Without normalization, indices and split boundaries break when k > n.