Loading…

mediumArraysLC #189Frequently asked

Rotate Array

Q: How do you solve Rotate Array using the Extra Array via Index Mapping (Brute / Correctness Proof) approach?

When to use it: Say this first — it's the cleanest proof of WHERE each element goes. Then pivot to the O(1)-space follow-up. The most reliable way to *understand* the rotation is to write the destination of each element as a closed-form index, then just place elements there. **The mapping is the entire problem.** A right rotation by `k` sends the element at index `i` to index `(i + k) mod n`. The `mod n` is what implements the wrap-around: when `i + k` runs off the end, it cycles back to the front. Element `n−1` with `k = 3`, `n = 7` goes to `(6 + 3) % 7 = 2`, which is exactly where the old last element should land after three elements wrap around. Filling a fresh array by this rule can't go wrong — there's no shifting, no overwriting order to worry about, every element is dropped directly into its final home. **Why `k %= n` matters even here.** If `k ≥ n`, `(i + k) % n` still works mathematically, but reducing `k` first keeps the intent obvious and avoids surprises in languages where `%` on large values is awkward. It also makes the connection to the three-reversal method (which *requires* `k < n` for the split point) explicit. **Why this isn't the final answer.** The interviewer's follow-up is almost always 'can you do it with O(1) extra space?'. The temp array is O(n) memory we'd love to avoid. But this version earns its keep: it gives you an unambiguous correctness reference to check the trickier in-place method against. State it, then say 'we can avoid the extra array with reversals.' Time complexity: O(n). Space complexity: O(n).

LCPractice

Two Pointers · 17 of 30 · 9 min

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Do it in-place with O(1) extra space if you can — that's the follow-up the interviewer cares about.

In plain English

Shift every element k positions to the right, wrapping the last k elements around to the front. Element originally at index i ends at index (i + k) % n. Because k may exceed n, reduce it modulo n before doing any work.

Examples

Example 1

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Note: The last 3 elements (5,6,7) wrap to the front; the first 4 shift right by 3.

Example 2

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Note: Last 2 elements (3,99) move to the front.

Example 3

Input: nums = [1,2], k = 3
Output: [2,1]
Note: k %= n → 3 % 2 = 1, so a single right rotation.

Constraints

1 ≤ nums.length ≤ 10⁵
-2³¹ ≤ nums[i] ≤ 2³¹ − 1
0 ≤ k ≤ 10⁵

Clarifying questions4First question: Can k be larger than the array length?Explore questions

Q1.Can k be larger than the array length?
Yes — k ≤ 10⁵ regardless of n. Rotating by n returns the original, so the effective rotation is k %= n. Skipping this causes out-of-bounds or wasted work.
Q2.Right rotation or left?
Right. The last k elements wrap to the front. A left rotation by k is equivalent to a right rotation by n − k, so the same machinery applies.
Q3.Is O(1) extra space required?
It's the follow-up that distinguishes answers. The extra-array copy is accepted, but the three-reversal method is what they're probing for.
Q4.Can the array contain duplicates or negatives?
Yes, both. Rotation only moves positions, so values are irrelevant to correctness.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Rotate the array right by k steps in-place. First reduce k with k %= n (k can exceed n). The O(1)-space trick is three reversals: reverse the whole array, then reverse the first k elements, then reverse the remaining n−k. That lands every element in its rotated position without an auxiliary array. O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you remember k %= n, and whether you know the three-reversal O(1)-space rotation rather than only the easy extra-array copy.

Where candidates slip

Forgetting k %= n (TLE or out-of-bounds when k > n), or rotating one element at a time k times, which is O(n·k).

How to stand out

Start with the O(n)-space index map to prove correctness, then deliver the three-reversal O(1) method and explain WHY the reversals compose into a rotation.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Extra Array via Index Mapping (Brute / Correctness Proof)	`O(n)`	`O(n)`	Say this first — it's the cleanest proof of WHERE each element goes. Then pivot to the O(1)-space follow-up.	Read
2	Three Reversals (Optimal, O(1) Space)Optimal	`O(n)`	`O(1)`	The answer they want for the O(1)-space follow-up. Explain WHY the reversals compose into a rotation — don't just recite the three calls.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewRotate array right by k stepsExtra O(n) space allowed?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Extra Array via Index Mapping (Brute / Correctness Proof)

TimeO(n)SpaceO(n)

Say this first — it's the cleanest proof of WHERE each element goes. Then pivot to the O(1)-space follow-up.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Where does the element at index i end up after a right rotation by k? Write the destination index as a formula.

2Hint 2Explore hint

Element i moves to (i + k) % n. Allocate a fresh array and place each element directly at its destination.

3Hint 3Explore hint

Copy the result back into nums so the rotation is 'in-place' from the caller's view, even though we used a temp array.

A · Core idea

The most reliable way to understand the rotation is to write the destination of each element as a closed-form index, then just place elements there.

The mapping is the entire problem. A right rotation by k sends the element at index i to index (i + k) mod n. The mod n is what implements the wrap-around: when i + k runs off the end, it cycles back to the front. Element n−1 with k = 3, n = 7 goes to (6 + 3) % 7 = 2, which is exactly where the old last element should land after three elements wrap around. Filling a fresh array by this rule can't go wrong — there's no shifting, no overwriting order to worry about, every element is dropped directly into its final home.

Why `k %= n` matters even here. If k ≥ n, (i + k) % n still works mathematically, but reducing k first keeps the intent obvious and avoids surprises in languages where % on large values is awkward. It also makes the connection to the three-reversal method (which requires k < n for the split point) explicit.

Why this isn't the final answer. The interviewer's follow-up is almost always 'can you do it with O(1) extra space?'. The temp array is O(n) memory we'd love to avoid. But this version earns its keep: it gives you an unambiguous correctness reference to check the trickier in-place method against. State it, then say 'we can avoid the extra array with reversals.'

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1,2,3,4,5,6,7], k = 3

i=0

out[3] = 1

Stateout = [_,_,_,1,_,_,_]

Final result[5,6,7,1,2,3,4]

C · Code with teaching comments

Reference implementation previewpublic void rotate(int[] nums, int k) { int n = nums.length; k %= n; int[] out = new int[n]; for (int i = 0; i < n; i++) {Explore the full code

solution.javaJava

Extra Array via Index Mapping (Brute / Correctness Proof) — reference

3 teaching notes

1
public void rotate(int[] nums, int k) {
2
    int n = nums.length;
3
    // Collapse rotations of full multiples of n; k can exceed n.
4
    k %= n;
5
    int[] out = new int[n];
6
    for (int i = 0; i < n; i++) {
7
        // Place each element at its rotated destination; %n wraps around.
8
        out[(i + k) % n] = nums[i];
9
    }
10
    // Copy back so the caller sees nums mutated in place.
11
    System.arraycopy(out, 0, nums, 0, n);
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Naming the destination formula (i + k) % n converts a vague 'shift things over' into a precise placement rule. Every correct rotation method must reproduce this mapping — it's your ground truth.

ComplexityO(n) time, O(n) space — One pass to fill the temp array plus one pass to copy back → O(n) time. The temp array of size n → O(n) extra space.

E · Edge cases and pitfalls5nums = [1], k = 100 — k %= 1 = 0 → out[i] = nums[i] → unchanged.Explore edge cases

Edge cases handled

nums = [1], k = 100k %= 1 = 0 → out[i] = nums[i] → unchanged.
k = 0Every element maps to its own index → array unchanged.

Pitfalls

Using `return nums[:]` in Python or reassigning nums = out — that rebinds the local name and doesn't mutate the caller's list; use nums[:] = out.
Skipping k %= n and indexing out of range when k > n.
Claiming this is O(1) space — it isn't; be honest about the temp array.

03.2

Approach 2 of 2 · Optimal

Three Reversals (Optimal, O(1) Space)

TimeO(n)SpaceO(1)

The answer they want for the O(1)-space follow-up. Explain WHY the reversals compose into a rotation — don't just recite the three calls.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

After k %= n, the answer is the last k elements followed by the first n−k elements. What does reversing the entire array do to those two blocks?

2Hint 2Explore hint

Reverse the whole array: now the last k elements are at the front but in reversed order, and the first n−k are at the back, also reversed.

3Hint 3Explore hint

Reverse the first k elements to fix their order, then reverse the remaining n−k to fix theirs. Three in-place reversals, each a two-pointer swap.

A · Core idea

The target layout after a right rotation by k is: last `k` elements, then first `n−k` elements, each block keeping its internal order. The three-reversal trick reaches that layout using only swaps.

Step 1 — reverse the whole array. Take [1,2,3,4,5,6,7] with k = 3. Reversing everything gives [7,6,5,4,3,2,1]. Look at what happened structurally: the last k = 3 elements (5,6,7) are now at the front — exactly where they belong — but in reversed order (7,6,5). Likewise the first n−k = 4 elements (1,2,3,4) are now at the back, reversed to (4,3,2,1). So one global reverse puts both blocks in the right region but with their internal order flipped.

Step 2 — reverse the first `k`. Reversing nums[0..k) un-flips the front block: [7,6,5] → [5,6,7]. The array is now [5,6,7,4,3,2,1]. The front is finished.

Step 3 — reverse the last `n−k`. Reversing nums[k..n) un-flips the back block: [4,3,2,1] → [1,2,3,4], giving [5,6,7,1,2,3,4] — the rotation, done.

Why this composes correctly in general. Reversal is an involution that maps position j within a segment to its mirror. Doing it globally then locally is algebraically equivalent to a cyclic shift: the global reverse sends index i to n−1−i; reversing the two sub-segments then sends each element to precisely (i + k) mod n — the same destination the index-map method computed. That equivalence is why you can trust it matches the brute-force ground truth.

Why `k %= n` is mandatory here. The split point for steps 2 and 3 is index k. If k ≥ n, that split is out of bounds and the reversals are nonsensical. Reducing k modulo n first guarantees 0 ≤ k < n so the two sub-segments are well-defined (and k = 0 becomes three no-op reverses, correctly leaving the array unchanged).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1,2,3,4,5,6,7], k = 3

Array state

start

original

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result[5,6,7,1,2,3,4]

C · Code with teaching comments

solution.javaJava

Three Reversals (Optimal, O(1) Space) — optimal

4 teaching notes

1
public void rotate(int[] nums, int k) {
2
    int n = nums.length;
3
    // Guarantees 0 <= k < n so the split index k is in bounds.
4
    k %= n;
5
    // Whole-array reverse: both blocks land in the right half, internally flipped.
6
    reverse(nums, 0, n - 1);
7
    // Un-flip the front block (the rotated-in suffix).
8
    reverse(nums, 0, k - 1);
9
    // Un-flip the back block (the rotated-out prefix).
10
    reverse(nums, k, n - 1);
11
}
12
 
13
private void reverse(int[] nums, int lo, int hi) {
14
    while (lo < hi) {
15
        int tmp = nums[lo];
16
        nums[lo] = nums[hi];
17
        nums[hi] = tmp;
18
        lo++;
19
        hi--;
20
    }
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Reverse-all-then-reverse-blocks is the canonical O(1)-space way to translate or rotate a sequence. The global reverse parks each block in the correct half; two local reverses repair the internal order. The same three-step move rotates strings and reorders words in a sentence.

ComplexityO(n) time, O(1) space — Each element is touched by exactly one reversal (the whole-array reverse counts as one), so total swaps ≈ n → O(n) time. Reversal swaps in place with two indices → O(1) space.

E · Edge cases and pitfalls6nums = [1,2], k = 3 — k %= 2 = 1 → reverse(0,1)→[2,1], reverse(0,0) no-op, reverse(1,1) no-op → [2,1].Explore edge cases

Edge cases handled

nums = [1,2], k = 3k %= 2 = 1 → reverse(0,1)→[2,1], reverse(0,0) no-op, reverse(1,1) no-op → [2,1].
k % n == 0k becomes 0 → reverse(0,n-1) then reverse(0,-1) and reverse(0,n-1): the two full reverses cancel, leaving the array unchanged.
nums = [9], k = 5k %= 1 = 0 → all reverses are no-ops → [9].

Pitfalls

Forgetting k %= n — reverse(0, k-1) with k > n is out of bounds.
Reversing the blocks before the whole array — rotates left instead of right.
Off-by-one in the reverse bounds: it's reverse(0, k-1) and reverse(k, n-1), inclusive endpoints.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic void rotate(int[] nums, int k) { int n = nums.length; k %= n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Skipping k %= n

k can be up to 10⁵ regardless of n. Without reduction, reverse(0, k-1) indexes past the array (Java throws) and a step-by-step rotation does k full passes (TLE).

Explore the code comparison

Don't write this

public void rotate(int[] nums, int k) {
    int n = nums.length;
    reverse(nums, 0, n - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, n - 1);
}

Write this instead

public void rotate(int[] nums, int k) {
    int n = nums.length;
    k %= n;
    reverse(nums, 0, n - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, n - 1);
}

Rebinding instead of mutating in Python

rotate must mutate nums in place. Assigning nums = out (or returning a new list) only changes the local reference; the caller's array is untouched.

Explore the code comparison

Don't write this

def rotate(self, nums, k):
    k %= len(nums)
    nums = nums[-k:] + nums[:-k]

Write this instead

def rotate(self, nums, k):
    k %= len(nums)
    nums[:] = nums[-k:] + nums[:-k]

One-step-at-a-time rotation

Popping the last element and inserting it at the front k times is O(n) per step → O(n·k). With n,k up to 1e5 that's 1e10 operations — TLE.

Explore the code comparison

Don't write this

for _ in range(k):
    nums.insert(0, nums.pop())

Write this instead

k %= len(nums)
nums[:] = nums[-k:] + nums[:-k]  # or the three-reversal method

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Reverse-whole then reverse-two-parts (in-place rotation)

Code pattern to memorize

k %= n
reverse(nums, 0, n - 1)
reverse(nums, 0, k - 1)
reverse(nums, k, n - 1)

Rules to remember

1Always `k %= n` first — k can be larger than n, and rotating by n is a no-op.
2Right-rotate by k means the last k elements move to the front, in their original order.
3Three reversals: whole → first k → last n−k. Doing first-k before the whole reversal rotates the wrong way.
4The reversal swaps are a two-pointer walk from both ends toward the middle — O(1) space.
5The extra-array method is O(n) space but the clearest correctness proof: out[(i + k) % n] = nums[i].

Use this pattern when

Cyclically shift an array/string in-place with O(1) extra space
Any 'rotate by k' where k may exceed the length
Block-swap or array-realignment problems
When the interviewer bans an auxiliary array

Choose another pattern when

You may use O(n) extra space and want the simplest code → index-mapping copy
Rotation is conceptual only (just need element at rotated index) → compute (i - k) % n on read, don't move data
Linked list rotation → relink pointers, not reversals (LC 61)
2D matrix rotation → transpose + reflect, a different mechanic (LC 48)

Interview takeaway

Three reversals turn an O(n)-space rotation into O(1) space. The identity 'reverse all, then reverse each block' is the reusable insight — it also rotates strings and underlies the classic 'rotate words in a sentence' problem.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternReverse-all-then-reverse-blocks is the canonical O(1)-space rotation/translation of a sequence. Recognise it whenever you must cyclically shift an array or string in place. The destination identity (i + k) % n is the correctness anchor.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Rotate List
Coming soon
Linked list: form a cycle, find the new tail at length - k%length, then break the cycle.
Rotate Image
Coming soon
2D 90° rotation = transpose then reverse each row, all in place.
Reverse Words in a String II
Coming soon
Same reverse-all-then-reverse-blocks idea applied to words in a char array.
Rotate Function
Coming soon
Derive F(k) from F(k-1) with a recurrence instead of materializing each rotation.

Same pattern

←

Remove Element

Continue · Next problem

Arrays: Left Rotation

mediumArraysLC #189Frequently asked

Rotate Array

LCPractice

Two Pointers · 17 of 30 · 9 min

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Do it in-place with O(1) extra space if you can — that's the follow-up the interviewer cares about.

In plain English

Examples

Example 1

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Note: The last 3 elements (5,6,7) wrap to the front; the first 4 shift right by 3.

Example 2

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Note: Last 2 elements (3,99) move to the front.

Example 3

Input: nums = [1,2], k = 3
Output: [2,1]
Note: k %= n → 3 % 2 = 1, so a single right rotation.

Constraints

1 ≤ nums.length ≤ 10⁵
-2³¹ ≤ nums[i] ≤ 2³¹ − 1
0 ≤ k ≤ 10⁵

Clarifying questions4First question: Can k be larger than the array length?Explore questions

Q1.Can k be larger than the array length?
Yes — k ≤ 10⁵ regardless of n. Rotating by n returns the original, so the effective rotation is k %= n. Skipping this causes out-of-bounds or wasted work.
Q2.Right rotation or left?
Right. The last k elements wrap to the front. A left rotation by k is equivalent to a right rotation by n − k, so the same machinery applies.
Q3.Is O(1) extra space required?
It's the follow-up that distinguishes answers. The extra-array copy is accepted, but the three-reversal method is what they're probing for.
Q4.Can the array contain duplicates or negatives?
Yes, both. Rotation only moves positions, so values are irrelevant to correctness.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you remember k %= n, and whether you know the three-reversal O(1)-space rotation rather than only the easy extra-array copy.

Where candidates slip

Forgetting k %= n (TLE or out-of-bounds when k > n), or rotating one element at a time k times, which is O(n·k).

How to stand out

Start with the O(n)-space index map to prove correctness, then deliver the three-reversal O(1) method and explain WHY the reversals compose into a rotation.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Extra Array via Index Mapping (Brute / Correctness Proof)	`O(n)`	`O(n)`	Say this first — it's the cleanest proof of WHERE each element goes. Then pivot to the O(1)-space follow-up.	Read
2	Three Reversals (Optimal, O(1) Space)Optimal	`O(n)`	`O(1)`	The answer they want for the O(1)-space follow-up. Explain WHY the reversals compose into a rotation — don't just recite the three calls.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Extra Array via Index Mapping (Brute / Correctness Proof)

TimeO(n)SpaceO(n)

Say this first — it's the cleanest proof of WHERE each element goes. Then pivot to the O(1)-space follow-up.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Where does the element at index i end up after a right rotation by k? Write the destination index as a formula.

2Hint 2Explore hint

Element i moves to (i + k) % n. Allocate a fresh array and place each element directly at its destination.

3Hint 3Explore hint

Copy the result back into nums so the rotation is 'in-place' from the caller's view, even though we used a temp array.

A · Core idea

The most reliable way to understand the rotation is to write the destination of each element as a closed-form index, then just place elements there.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1,2,3,4,5,6,7], k = 3

i=0

out[3] = 1

Stateout = [_,_,_,1,_,_,_]

Final result[5,6,7,1,2,3,4]

C · Code with teaching comments

Reference implementation previewpublic void rotate(int[] nums, int k) { int n = nums.length; k %= n; int[] out = new int[n]; for (int i = 0; i < n; i++) {Explore the full code

solution.javaJava

Extra Array via Index Mapping (Brute / Correctness Proof) — reference

3 teaching notes

1
public void rotate(int[] nums, int k) {
2
    int n = nums.length;
3
    // Collapse rotations of full multiples of n; k can exceed n.
4
    k %= n;
5
    int[] out = new int[n];
6
    for (int i = 0; i < n; i++) {
7
        // Place each element at its rotated destination; %n wraps around.
8
        out[(i + k) % n] = nums[i];
9
    }
10
    // Copy back so the caller sees nums mutated in place.
11
    System.arraycopy(out, 0, nums, 0, n);
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Naming the destination formula (i + k) % n converts a vague 'shift things over' into a precise placement rule. Every correct rotation method must reproduce this mapping — it's your ground truth.

ComplexityO(n) time, O(n) space — One pass to fill the temp array plus one pass to copy back → O(n) time. The temp array of size n → O(n) extra space.

E · Edge cases and pitfalls5nums = [1], k = 100 — k %= 1 = 0 → out[i] = nums[i] → unchanged.Explore edge cases

Edge cases handled

nums = [1], k = 100k %= 1 = 0 → out[i] = nums[i] → unchanged.
k = 0Every element maps to its own index → array unchanged.

Pitfalls

Using `return nums[:]` in Python or reassigning nums = out — that rebinds the local name and doesn't mutate the caller's list; use nums[:] = out.
Skipping k %= n and indexing out of range when k > n.
Claiming this is O(1) space — it isn't; be honest about the temp array.

03.2

Approach 2 of 2 · Optimal

Three Reversals (Optimal, O(1) Space)

TimeO(n)SpaceO(1)

The answer they want for the O(1)-space follow-up. Explain WHY the reversals compose into a rotation — don't just recite the three calls.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

After k %= n, the answer is the last k elements followed by the first n−k elements. What does reversing the entire array do to those two blocks?

2Hint 2Explore hint

Reverse the whole array: now the last k elements are at the front but in reversed order, and the first n−k are at the back, also reversed.

3Hint 3Explore hint

Reverse the first k elements to fix their order, then reverse the remaining n−k to fix theirs. Three in-place reversals, each a two-pointer swap.

A · Core idea

Step 2 — reverse the first `k`. Reversing nums[0..k) un-flips the front block: [7,6,5] → [5,6,7]. The array is now [5,6,7,4,3,2,1]. The front is finished.

Step 3 — reverse the last `n−k`. Reversing nums[k..n) un-flips the back block: [4,3,2,1] → [1,2,3,4], giving [5,6,7,1,2,3,4] — the rotation, done.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1,2,3,4,5,6,7], k = 3

Array state

start

original

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result[5,6,7,1,2,3,4]

C · Code with teaching comments

solution.javaJava

Three Reversals (Optimal, O(1) Space) — optimal

4 teaching notes

1
public void rotate(int[] nums, int k) {
2
    int n = nums.length;
3
    // Guarantees 0 <= k < n so the split index k is in bounds.
4
    k %= n;
5
    // Whole-array reverse: both blocks land in the right half, internally flipped.
6
    reverse(nums, 0, n - 1);
7
    // Un-flip the front block (the rotated-in suffix).
8
    reverse(nums, 0, k - 1);
9
    // Un-flip the back block (the rotated-out prefix).
10
    reverse(nums, k, n - 1);
11
}
12
 
13
private void reverse(int[] nums, int lo, int hi) {
14
    while (lo < hi) {
15
        int tmp = nums[lo];
16
        nums[lo] = nums[hi];
17
        nums[hi] = tmp;
18
        lo++;
19
        hi--;
20
    }
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6nums = [1,2], k = 3 — k %= 2 = 1 → reverse(0,1)→[2,1], reverse(0,0) no-op, reverse(1,1) no-op → [2,1].Explore edge cases

Edge cases handled

nums = [1,2], k = 3k %= 2 = 1 → reverse(0,1)→[2,1], reverse(0,0) no-op, reverse(1,1) no-op → [2,1].
k % n == 0k becomes 0 → reverse(0,n-1) then reverse(0,-1) and reverse(0,n-1): the two full reverses cancel, leaving the array unchanged.
nums = [9], k = 5k %= 1 = 0 → all reverses are no-ops → [9].

Pitfalls

Forgetting k %= n — reverse(0, k-1) with k > n is out of bounds.
Reversing the blocks before the whole array — rotates left instead of right.
Off-by-one in the reverse bounds: it's reverse(0, k-1) and reverse(k, n-1), inclusive endpoints.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic void rotate(int[] nums, int k) { int n = nums.length; k %= n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Skipping k %= n

k can be up to 10⁵ regardless of n. Without reduction, reverse(0, k-1) indexes past the array (Java throws) and a step-by-step rotation does k full passes (TLE).

Explore the code comparison

Don't write this

public void rotate(int[] nums, int k) {
    int n = nums.length;
    reverse(nums, 0, n - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, n - 1);
}

Write this instead

public void rotate(int[] nums, int k) {
    int n = nums.length;
    k %= n;
    reverse(nums, 0, n - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, n - 1);
}

Rebinding instead of mutating in Python

rotate must mutate nums in place. Assigning nums = out (or returning a new list) only changes the local reference; the caller's array is untouched.

Explore the code comparison

Don't write this

def rotate(self, nums, k):
    k %= len(nums)
    nums = nums[-k:] + nums[:-k]

Write this instead

def rotate(self, nums, k):
    k %= len(nums)
    nums[:] = nums[-k:] + nums[:-k]

One-step-at-a-time rotation

Popping the last element and inserting it at the front k times is O(n) per step → O(n·k). With n,k up to 1e5 that's 1e10 operations — TLE.

Explore the code comparison

Don't write this

for _ in range(k):
    nums.insert(0, nums.pop())

Write this instead

k %= len(nums)
nums[:] = nums[-k:] + nums[:-k]  # or the three-reversal method

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Reverse-whole then reverse-two-parts (in-place rotation)

Code pattern to memorize

k %= n
reverse(nums, 0, n - 1)
reverse(nums, 0, k - 1)
reverse(nums, k, n - 1)

Rules to remember

1Always `k %= n` first — k can be larger than n, and rotating by n is a no-op.
2Right-rotate by k means the last k elements move to the front, in their original order.
3Three reversals: whole → first k → last n−k. Doing first-k before the whole reversal rotates the wrong way.
4The reversal swaps are a two-pointer walk from both ends toward the middle — O(1) space.
5The extra-array method is O(n) space but the clearest correctness proof: out[(i + k) % n] = nums[i].

Use this pattern when

Cyclically shift an array/string in-place with O(1) extra space
Any 'rotate by k' where k may exceed the length
Block-swap or array-realignment problems
When the interviewer bans an auxiliary array

Choose another pattern when

You may use O(n) extra space and want the simplest code → index-mapping copy
Rotation is conceptual only (just need element at rotated index) → compute (i - k) % n on read, don't move data
Linked list rotation → relink pointers, not reversals (LC 61)
2D matrix rotation → transpose + reflect, a different mechanic (LC 48)

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Rotate List
Coming soon
Linked list: form a cycle, find the new tail at length - k%length, then break the cycle.
Rotate Image
Coming soon
2D 90° rotation = transpose then reverse each row, all in place.
Reverse Words in a String II
Coming soon
Same reverse-all-then-reverse-blocks idea applied to words in a char array.
Rotate Function
Coming soon
Derive F(k) from F(k-1) with a recurrence instead of materializing each rotation.

Same pattern

←

Remove Element

Continue · Next problem

Arrays: Left Rotation