Loading…

easyArraysFrequently asked

Arrays: Left Rotation

Q: How do you solve Arrays: Left Rotation using the Brute Force — Rotate One Step at a Time approach?

When to use it: Mention it to anchor the definition ('a left rotation shifts everything by one'), then immediately flag that repeating it d times is O(n·d) and won't scale. The literal reading of the prompt is 'perform d left rotations,' where one left rotation moves every element one slot toward the front. So implement a single rotation — stash `a[0]`, shift `a[1..n-1]` down into `a[0..n-2]`, drop the stashed value into `a[n-1]` — and run it `d` times. **Why it's the natural first attempt.** It mirrors the problem statement one-to-one, so it's obviously correct and easy to reason about. Great for explaining *what* a rotation is. **Why it doesn't scale.** Every single rotation touches all `n` elements, and you do that `d` times, so the cost is `O(n·d)`. When `d` is close to `n` (allowed by the constraints), that's quadratic — about `10¹⁰` operations at the limits, which times out. The deeper problem is that it re-moves the same elements over and over; after `d` rotations each element has been copied `d` times, when it only ever needed to move once. That waste is the cue to compute each element's *final* destination directly, which the optimal approaches do. Time complexity: O(n·d). Space complexity: O(1).

Q: How do you solve Arrays: Left Rotation using the Index Math — Remap Into a New Array (Optimal, O(n) space) approach?

When to use it: The cleanest answer. Phrase it as 'each element's final index is a closed-form (i ± d) mod n, so I place it in one pass.' Compute each element's destination directly and write it into a fresh array in one pass — no repeated shifting. **Deriving the formula.** One left rotation sends index `i` to `i - 1` (mod n). Doing that `d` times sends `i` to `i - d` (mod n). To keep the index non-negative we write `(i - d + n) % n`. Equivalently, we can fill the destination directly: new position `i` should contain whatever ends up there, which is the old element at `(i + d) % n`. Both conventions describe the same rotation; pick one and apply it uniformly. The 'fill destination' form `result[i] = a[(i + d) % n]` is usually cleanest because the loop variable `i` indexes the output left to right. **Why reduce `d %= n` first.** Rotating by `n` returns the original array, so only `d mod n` rotations are meaningful. Reducing up front avoids redundant arithmetic and guarantees the index stays in `[0, n)`. At the constraint `d ≤ n`, this also turns `d == n` into `d == 0` (a no-op) instead of a wasted full cycle. **Why this is correct and fast.** Every element is read once and written exactly once to its final slot — no element moves twice. That's the whole improvement over brute force: we replaced `d` rounds of moving with one round of *computing where each element belongs*. **The one cost.** It uses a second array of size `n`. If the interviewer forbids that, the three-reversal method below achieves the same rotation in place with `O(1)` extra space. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Arrays: Left Rotation using the Three Reversals — In-Place Rotation (Optimal, O(1) space) approach?

When to use it: Bring this out when O(1) extra space is required. Explain why reversing the two halves then the whole array equals a rotation. Rotate in place using three in-bounds reversals, no auxiliary array. **The construction.** A left rotation by `d` should produce `a[d..n-1]` followed by `a[0..d-1]`. The reversal trick builds exactly that: (1) reverse `a[0..d-1]`, (2) reverse `a[d..n-1]`, (3) reverse the whole array `a[0..n-1]`. **Why three reversals compose into a rotation.** Think of the array as two blocks `X = a[0..d-1]` and `Y = a[d..n-1]`; we want `Y X`. Reversing each block gives `Xᴿ Yᴿ`. Reversing the entire result flips the order of the two blocks *and* un-reverses each one: `(Xᴿ Yᴿ)ᴿ = (Yᴿ)ᴿ (Xᴿ)ᴿ = Y X`. That's precisely the rotated array. The double-reversal cancels within each block while the outer reversal swaps the blocks — elegant and exact. **Why reduce `d %= n` first.** Same reason as before: a rotation by a multiple of `n` is the identity. Reducing also keeps the split point `d` inside the array so the sub-range reversals stay in bounds. **Why O(1) space.** Each reversal is a two-pointer swap walking inward, mutating the array directly. No copy is made, so only a couple of index variables are used. Time complexity: O(n). Space complexity: O(1).

Two Pointers · 18 of 30 · 7 min

A left rotation operation on an array shifts each of the array's elements 1 unit to the left. For example, if 2 left rotations are performed on array [1, 2, 3, 4, 5], the array becomes [3, 4, 5, 1, 2].

Given an array a of n integers and a number d, perform d left rotations on the array and return the resulting array.

In plain English

Shift every element d positions toward index 0, with the first d elements wrapping around to the back. Position-wise, the new array is a[d], a[d+1], …, a[n-1], a[0], …, a[d-1]. The whole task is a cyclic relabeling of indices.

Examples

Example 1

Input: a = [1, 2, 3, 4, 5], d = 2
Output: [3, 4, 5, 1, 2]
Note: Each element moves 2 slots left; 1 and 2 wrap to the end.

Example 2

Input: a = [1, 2, 3, 4, 5], d = 5
Output: [1, 2, 3, 4, 5]
Note: Rotating by n (= 5) is a full cycle → unchanged. This is why d %= n matters.

Example 3

Input: a = [1, 2], d = 1
Output: [2, 1]
Note: A single left rotation swaps the two elements.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ d ≤ n
1 ≤ a[i] ≤ 10⁶
Elements may repeat

Clarifying questions4First question: Is d guaranteed to be ≤ n, or could it be larger?Explore questions

Q1.Is d guaranteed to be ≤ n, or could it be larger?
Here d ≤ n, but you should still write d %= n defensively — rotating by n returns the array unchanged, and the mod makes any d work.
Q2.Do I have to rotate in place, or can I return a new array?
Returning a new array is fine and simplest (O(n) space). If the interviewer demands O(1) extra space, switch to the three-reversal trick.
Q3.Left or right rotation?
Left: front elements move to the back. A left rotation by d equals a right rotation by n - d — worth confirming so you don't invert the direction.
Q4.Can the array contain duplicates or negatives?
Yes; rotation is purely positional, so values are irrelevant to the logic.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Left-rotating by d moves each element d slots toward the front, wrapping around. The naive O(n·d) shifts one step at a time. The clean O(n) answer is pure index math: element originally at index i lands at (i - d) mod n, or equivalently the new array's position i holds the old element at (i + d) mod n. For O(1) extra space, use the three-reversal trick: reverse [0, d), reverse [d, n), then reverse the whole array.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can express a rotation as a closed-form modular index map instead of repeated single-step shifts, and whether you know the in-place three-reversal technique for the O(1)-space variant.

Where candidates slip

O(n·d) one-step-at-a-time shifting (times out for large d), forgetting d %= n, or getting the sign wrong so you right-rotate instead of left-rotate.

How to stand out

Derive the index formula out loud, reduce d %= n first, then offer the three-reversal in-place method for O(1) space and explain why three 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	Brute Force — Rotate One Step at a Time	`O(n·d)`	`O(1)`	Mention it to anchor the definition ('a left rotation shifts everything by one'), then immediately flag that repeating it d times is O(n·d) and won't scale.	Read
2	Index Math — Remap Into a New Array (Optimal, O(n) space)Optimal	`O(n)`	`O(n)`	The cleanest answer. Phrase it as 'each element's final index is a closed-form (i ± d) mod n, so I place it in one pass.'	Read
3	Three Reversals — In-Place Rotation (Optimal, O(1) space)	`O(n)`	`O(1)`	Bring this out when O(1) extra space is required. Explain why reversing the two halves then the whole array equals a rotation.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewLeft-rotate by dO(1) extra space required?NoYesExplore 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 3

Brute Force — Rotate One Step at a Time

TimeO(n·d)SpaceO(1)

Mention it to anchor the definition ('a left rotation shifts everything by one'), then immediately flag that repeating it d times is O(n·d) and won't scale.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The problem defines a single left rotation: every element moves one slot left and the first element wraps to the back. Can you do exactly that once?

2Hint 2Explore hint

Save the first element, shift everything left by one, then place the saved element at the end.

3Hint 3Explore hint

Now repeat that single-rotation routine d times. What's the total cost?

A · Core idea

The literal reading of the prompt is 'perform d left rotations,' where one left rotation moves every element one slot toward the front. So implement a single rotation — stash a[0], shift a[1..n-1] down into a[0..n-2], drop the stashed value into a[n-1] — and run it d times.

Why it's the natural first attempt. It mirrors the problem statement one-to-one, so it's obviously correct and easy to reason about. Great for explaining what a rotation is.

Why it doesn't scale. Every single rotation touches all n elements, and you do that d times, so the cost is O(n·d). When d is close to n (allowed by the constraints), that's quadratic — about 10¹⁰ operations at the limits, which times out. The deeper problem is that it re-moves the same elements over and over; after d rotations each element has been copied d times, when it only ever needed to move once. That waste is the cue to compute each element's final destination directly, which the optimal approaches do.

B · Visual dry run

Interactive dry run

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

a = [1, 2, 3, 4, 5], d = 2

Array state

after rotation 1

1 wraps to the back

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

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

C · Code with teaching comments

Reference implementation previewpublic List<Integer> rotateLeft(int d, List<Integer> a) { int n = a.size(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = a.get(i);Explore the full code

solution.javaJava

Brute Force — Rotate One Step at a Time — reference

3 teaching notes

1
public List<Integer> rotateLeft(int d, List<Integer> a) {
2
    int n = a.size();
3
    int[] arr = new int[n];
4
    for (int i = 0; i < n; i++) {
5
        arr[i] = a.get(i);
6
    }
7
    for (int r = 0; r < d; r++) {
8
        // Stash the front element before it gets overwritten by the shift.
9
        int first = arr[0];
10
        for (int i = 1; i < n; i++) {
11
            // Shift everything one slot left — the core of a single rotation.
12
            arr[i - 1] = arr[i];
13
        }
14
        // Wrap the old front element around to the back.
15
        arr[n - 1] = first;
16
    }
17
    List<Integer> result = new ArrayList<>(n);
18
    for (int v : arr) {
19
        result.add(v);
20
    }
21
    return result;
22
}

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

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

Repeating a one-step operation d times almost always hides a closed-form shortcut. Here, an element rotated d times ends up exactly d slots left — so compute that final position once instead of stepping it there d times.

ComplexityO(n·d) time, O(1) space — Each single rotation shifts all n elements once → O(n). Doing it d times gives O(n·d). For n = 10⁵ and d near n that's ~10¹⁰ operations — far too slow.

E · Edge cases and pitfalls3Times out for large d — O(n·d) is quadratic when d ≈ n.Explore edge cases

Pitfalls

Times out for large d — O(n·d) is quadratic when d ≈ n.
Overwriting arr[0] before stashing it, corrupting the shift.
Forgetting that d could equal n, doing a full pointless cycle instead of d %= n.

03.2

Approach 2 of 3 · Optimal

Index Math — Remap Into a New Array (Optimal, O(n) space)

TimeO(n)SpaceO(n)

The cleanest answer. Phrase it as 'each element's final index is a closed-form (i ± d) mod n, so I place it in one pass.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

After d left rotations, where does the element originally at index i end up? It moves d slots left, wrapping around.

2Hint 2Explore hint

Old index i lands at (i - d + n) % n. Equivalently, new position i should hold the old element at (i + d) % n.

3Hint 3Explore hint

Reduce d %= n first, then fill a result array in a single pass with one of those formulas.

A · Core idea

Compute each element's destination directly and write it into a fresh array in one pass — no repeated shifting.

Deriving the formula. One left rotation sends index i to i - 1 (mod n). Doing that d times sends i to i - d (mod n). To keep the index non-negative we write (i - d + n) % n. Equivalently, we can fill the destination directly: new position i should contain whatever ends up there, which is the old element at (i + d) % n. Both conventions describe the same rotation; pick one and apply it uniformly. The 'fill destination' form result[i] = a[(i + d) % n] is usually cleanest because the loop variable i indexes the output left to right.

Why reduce `d %= n` first. Rotating by n returns the original array, so only d mod n rotations are meaningful. Reducing up front avoids redundant arithmetic and guarantees the index stays in [0, n). At the constraint d ≤ n, this also turns d == n into d == 0 (a no-op) instead of a wasted full cycle.

Why this is correct and fast. Every element is read once and written exactly once to its final slot — no element moves twice. That's the whole improvement over brute force: we replaced d rounds of moving with one round of computing where each element belongs.

The one cost. It uses a second array of size n. If the interviewer forbids that, the three-reversal method below achieves the same rotation in place with O(1) extra space.

B · Visual dry run

Interactive dry run

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

a = [1, 2, 3, 4, 5], d = 2

Array state

source

original array; source indices 2,3,4,0,1 feed result 0..4

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

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

C · Code with teaching comments

solution.javaJava

Index Math — Remap Into a New Array (Optimal, O(n) space) — optimal

2 teaching notes

1
public List<Integer> rotateLeft(int d, List<Integer> a) {
2
    int n = a.size();
3
    // Collapse full cycles — rotating by n or a multiple is a no-op.
4
    d %= n;
5
    List<Integer> result = new ArrayList<>(Collections.nCopies(n, 0));
6
    for (int i = 0; i < n; i++) {
7
        // Destination i pulls the old element d slots ahead, wrapping via % n.
8
        result.set(i, a.get((i + d) % n));
9
    }
10
    return result;
11
}

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

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

Rotation is a relabeling of indices under addition mod n. Once you write the destination as a closed form, the loop becomes trivial and runs once. This 'compute the final position directly instead of simulating each step' move is the same insight behind fast modular exponentiation and any 'apply an operation k times' problem with a cyclic structure.

ComplexityO(n) time, O(n) space — A single pass computing one modular index and one assignment per element → O(n) time. The separate result array of size n → O(n) extra space.

E · Edge cases and pitfalls5a = [1, 2, 3], d = 3 — d %= 3 → 0, so result[i] = a[i] — the original array. Confirms full-cycle reduction.Explore edge cases

Edge cases handled

a = [1, 2, 3], d = 3d %= 3 → 0, so result[i] = a[i] — the original array. Confirms full-cycle reduction.
a = [7], d = 1n = 1, d %= 1 = 0 → unchanged single element. No mod-by-zero because n ≥ 1.

Pitfalls

Skipping d %= n and indexing out of range when d ≥ n.
Mixing the two conventions: result[(i - d + n) % n] = a[i] and result[i] = a[(i + d) % n] are both correct, but blending them scrambles the array.
Right-rotating by using (i - d) when you meant a left rotation's (i + d) for the destination-fill form.

03.3

Approach 3 of 3

Three Reversals — In-Place Rotation (Optimal, O(1) space)

TimeO(n)SpaceO(1)

Bring this out when O(1) extra space is required. Explain why reversing the two halves then the whole array equals a rotation.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Can you rotate without a second array? Think about what reversing sub-ranges does.

2Hint 2Explore hint

Reverse the first d elements, then reverse the remaining n - d elements.

3Hint 3Explore hint

Now reverse the entire array. The two halves swap places and each comes out in the correct order — that's a left rotation by d.

A · Core idea

Rotate in place using three in-bounds reversals, no auxiliary array.

The construction. A left rotation by d should produce a[d..n-1] followed by a[0..d-1]. The reversal trick builds exactly that: (1) reverse a[0..d-1], (2) reverse a[d..n-1], (3) reverse the whole array a[0..n-1].

Why three reversals compose into a rotation. Think of the array as two blocks X = a[0..d-1] and Y = a[d..n-1]; we want Y X. Reversing each block gives Xᴿ Yᴿ. Reversing the entire result flips the order of the two blocks and un-reverses each one: (Xᴿ Yᴿ)ᴿ = (Yᴿ)ᴿ (Xᴿ)ᴿ = Y X. That's precisely the rotated array. The double-reversal cancels within each block while the outer reversal swaps the blocks — elegant and exact.

Why reduce `d %= n` first. Same reason as before: a rotation by a multiple of n is the identity. Reducing also keeps the split point d inside the array so the sub-range reversals stay in bounds.

Why O(1) space. Each reversal is a two-pointer swap walking inward, mutating the array directly. No copy is made, so only a couple of index variables are used.

B · Visual dry run

Interactive dry run

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

a = [1, 2, 3, 4, 5], d = 2

Array state

reverse [0,2)

first block reversed

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

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

C · Code with teaching comments

solution.javaJava

Three Reversals — In-Place Rotation (Optimal, O(1) space) — reference

4 teaching notes

1
public List<Integer> rotateLeft(int d, List<Integer> a) {
2
    int n = a.size();
3
    int[] arr = new int[n];
4
    for (int i = 0; i < n; i++) {
5
        arr[i] = a.get(i);
6
    }
7
    // Keep the split point inside the array and skip full cycles.
8
    d %= n;
9
    // Reverse the first block X → Xᴿ.
10
    reverse(arr, 0, d - 1);
11
    // Reverse the second block Y → Yᴿ.
12
    reverse(arr, d, n - 1);
13
    // Reverse everything: (Xᴿ Yᴿ)ᴿ = Y X, the rotated array.
14
    reverse(arr, 0, n - 1);
15
    List<Integer> result = new ArrayList<>(n);
16
    for (int v : arr) {
17
        result.add(v);
18
    }
19
    return result;
20
}
21
 
22
private void reverse(int[] arr, int lo, int hi) {
23
    while (lo < hi) {
24
        int tmp = arr[lo];
25
        arr[lo] = arr[hi];
26
        arr[hi] = tmp;
27
        lo++;
28
        hi--;
29
    }
30
}

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

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

Reversal is the secret weapon for in-place rearrangement: reversing parts and then the whole composes block swaps without extra memory. The identity (Xᴿ Yᴿ)ᴿ = Y X is worth memorizing — it turns 'rotate in place with O(1) space' from a puzzle into three lines. The same trick rotates strings and underlies Rotate Array (LeetCode 189).

ComplexityO(n) time, O(1) space — Three reversals touch a total of n + (something ≤ n) elements, each a constant-time swap → O(n) time. Reversals are done with two-pointer swaps in place → O(1) extra space.

E · Edge cases and pitfalls5a = [1, 2, 3, 4], d = 4 — d %= 4 → 0. reverse(0,-1) is a no-op, reverse(0,3) then reverse(0,3) cancel → unchanged. Confirms d == n is the identity.Explore edge cases

Edge cases handled

a = [1, 2, 3, 4], d = 4d %= 4 → 0. reverse(0,-1) is a no-op, reverse(0,3) then reverse(0,3) cancel → unchanged. Confirms d == n is the identity.
a = [9, 8], d = 1reverse [0,0) no-op, reverse [1,1) no-op, reverse [0,1) swaps → [8, 9]. Minimal rotation works.

Pitfalls

Reversing the wrong sub-ranges or in the wrong order — only X then Y then whole yields a left rotation.
Off-by-one on the reverse bounds: use inclusive [d, n-1], not [d, n].
Forgetting d %= n so reverse(arr, 0, d-1) runs with d ≥ n and goes out of bounds.

Practice

Try the solution yourself

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

Editable code previewpublic List<Integer> rotateLeft(int d, List<Integer> a) { int n = a.size(); d %= n; List<Integer> result = new ArrayList<>(Collections.nCopies(n, 0)); for (int i = 0; i < n; i++) {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.

Quadratic one-step shifting

Calling a single-rotation routine d times copies every element d times. For d ≈ n that's O(n²) and times out. Compute the final index directly instead.

Explore the code comparison

Don't write this

for (int r = 0; r < d; r++) {
    int first = arr[0];
    for (int i = 1; i < n; i++) arr[i - 1] = arr[i];
    arr[n - 1] = first;
}

Write this instead

d %= n;
for (int i = 0; i < n; i++) {
    result[i] = arr[(i + d) % n];
}

Negative modulo in Java

Java's % returns a negative result for negative operands, so (i - d) % n can be negative and crash. Add n before the mod. (Python's % is already non-negative.)

Explore the code comparison

Don't write this

int dest = (i - d) % n;   // can be negative
result[dest] = arr[i];

Write this instead

int dest = (i - d + n) % n;
result[dest] = arr[i];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Modular index remap + three-reversal in-place rotation

Code pattern to memorize

# new array via index math
result[(i - d) % n] = a[i]   # element at i goes here
# or, fill destination directly:
result[i] = a[(i + d) % n]

# in-place three reversals (left rotate by d):
reverse(a, 0, d - 1)
reverse(a, d, n - 1)
reverse(a, 0, n - 1)

Rules to remember

1Always reduce the shift first: d %= n. A rotation by n (or any multiple) is the identity — skip the work and avoid mod-by-zero style bugs.
2Left rotation: the element at old index i moves to (i - d + n) % n; equivalently new position i pulls from old (i + d) % n. Pick one convention and stay consistent.
3The + n before % n matters in languages where % can go negative (Java) — Python's % is already non-negative.
4The three-reversal trick rotates in place in O(1) extra space: reverse the first d, reverse the rest, reverse everything.
5Left rotate by d and right rotate by n - d are the same operation — a common source of off-by-direction bugs.

Use this pattern when

Cyclically shift / rotate an array or string by a fixed offset
Wrap-around indexing problems ('the next element after the last is the first')
In-place rotation under an O(1) extra-space constraint → reversal trick
Any time you catch yourself shifting elements one at a time in a loop

Choose another pattern when

You only need to *read* rotated values, not materialize them → just index with (i + d) % n on the fly, no copy
Rotation amount changes every query → precompute or use a deque/offset pointer instead of physically moving data
Data is a linked list, not an array → relink nodes instead of index math

Interview takeaway

Rotation is modular arithmetic in disguise: every element's destination is a simple (i ± d) mod n. Once you see that, you never shift one-at-a-time again — you either remap into a new array in O(n) or do the three-reversal dance in place. The same wrap-around index trick powers circular buffers, Rotate Array, and string rotation checks.

Continue

Transfer the pattern to another problem

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

Transferable patternModular Index Remap + Reversal Rotation. Recognise it on any cyclic shift: each element's destination is (i ± d) mod n, so either fill a new array in O(n) or rotate in place with three reversals in O(1) space. Always reduce d %= n first. Same shape as Rotate Array and Rotate String.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Rotate Array
Right rotation in place — same three-reversal trick with the split at n - k.
Rotate String
Coming soon
Check if one string is a rotation of another via (s + s).contains(goal).
Rotate List
Coming soon
Same idea on a linked list — find the new tail with modular counting and relink.

←

Rotate Array

Continue · Next problem

Sorting: Bubble Sort

easyArraysFrequently asked

Arrays: Left Rotation

Two Pointers · 18 of 30 · 7 min

Given an array a of n integers and a number d, perform d left rotations on the array and return the resulting array.

In plain English

Examples

Example 1

Input: a = [1, 2, 3, 4, 5], d = 2
Output: [3, 4, 5, 1, 2]
Note: Each element moves 2 slots left; 1 and 2 wrap to the end.

Example 2

Input: a = [1, 2, 3, 4, 5], d = 5
Output: [1, 2, 3, 4, 5]
Note: Rotating by n (= 5) is a full cycle → unchanged. This is why d %= n matters.

Example 3

Input: a = [1, 2], d = 1
Output: [2, 1]
Note: A single left rotation swaps the two elements.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ d ≤ n
1 ≤ a[i] ≤ 10⁶
Elements may repeat

Clarifying questions4First question: Is d guaranteed to be ≤ n, or could it be larger?Explore questions

Q1.Is d guaranteed to be ≤ n, or could it be larger?
Here d ≤ n, but you should still write d %= n defensively — rotating by n returns the array unchanged, and the mod makes any d work.
Q2.Do I have to rotate in place, or can I return a new array?
Returning a new array is fine and simplest (O(n) space). If the interviewer demands O(1) extra space, switch to the three-reversal trick.
Q3.Left or right rotation?
Left: front elements move to the back. A left rotation by d equals a right rotation by n - d — worth confirming so you don't invert the direction.
Q4.Can the array contain duplicates or negatives?
Yes; rotation is purely positional, so values are irrelevant to the logic.

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 can express a rotation as a closed-form modular index map instead of repeated single-step shifts, and whether you know the in-place three-reversal technique for the O(1)-space variant.

Where candidates slip

O(n·d) one-step-at-a-time shifting (times out for large d), forgetting d %= n, or getting the sign wrong so you right-rotate instead of left-rotate.

How to stand out

Derive the index formula out loud, reduce d %= n first, then offer the three-reversal in-place method for O(1) space and explain why three 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	Brute Force — Rotate One Step at a Time	`O(n·d)`	`O(1)`	Mention it to anchor the definition ('a left rotation shifts everything by one'), then immediately flag that repeating it d times is O(n·d) and won't scale.	Read
2	Index Math — Remap Into a New Array (Optimal, O(n) space)Optimal	`O(n)`	`O(n)`	The cleanest answer. Phrase it as 'each element's final index is a closed-form (i ± d) mod n, so I place it in one pass.'	Read
3	Three Reversals — In-Place Rotation (Optimal, O(1) space)	`O(n)`	`O(1)`	Bring this out when O(1) extra space is required. Explain why reversing the two halves then the whole array equals a rotation.	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 3

Brute Force — Rotate One Step at a Time

TimeO(n·d)SpaceO(1)

Mention it to anchor the definition ('a left rotation shifts everything by one'), then immediately flag that repeating it d times is O(n·d) and won't scale.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The problem defines a single left rotation: every element moves one slot left and the first element wraps to the back. Can you do exactly that once?

2Hint 2Explore hint

Save the first element, shift everything left by one, then place the saved element at the end.

3Hint 3Explore hint

Now repeat that single-rotation routine d times. What's the total cost?

A · Core idea

Why it's the natural first attempt. It mirrors the problem statement one-to-one, so it's obviously correct and easy to reason about. Great for explaining what a rotation is.

B · Visual dry run

Interactive dry run

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

a = [1, 2, 3, 4, 5], d = 2

Array state

after rotation 1

1 wraps to the back

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

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

C · Code with teaching comments

solution.javaJava

Brute Force — Rotate One Step at a Time — reference

3 teaching notes

1
public List<Integer> rotateLeft(int d, List<Integer> a) {
2
    int n = a.size();
3
    int[] arr = new int[n];
4
    for (int i = 0; i < n; i++) {
5
        arr[i] = a.get(i);
6
    }
7
    for (int r = 0; r < d; r++) {
8
        // Stash the front element before it gets overwritten by the shift.
9
        int first = arr[0];
10
        for (int i = 1; i < n; i++) {
11
            // Shift everything one slot left — the core of a single rotation.
12
            arr[i - 1] = arr[i];
13
        }
14
        // Wrap the old front element around to the back.
15
        arr[n - 1] = first;
16
    }
17
    List<Integer> result = new ArrayList<>(n);
18
    for (int v : arr) {
19
        result.add(v);
20
    }
21
    return result;
22
}

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

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

E · Edge cases and pitfalls3Times out for large d — O(n·d) is quadratic when d ≈ n.Explore edge cases

Pitfalls

Times out for large d — O(n·d) is quadratic when d ≈ n.
Overwriting arr[0] before stashing it, corrupting the shift.
Forgetting that d could equal n, doing a full pointless cycle instead of d %= n.

03.2

Approach 2 of 3 · Optimal

Index Math — Remap Into a New Array (Optimal, O(n) space)

TimeO(n)SpaceO(n)

The cleanest answer. Phrase it as 'each element's final index is a closed-form (i ± d) mod n, so I place it in one pass.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

After d left rotations, where does the element originally at index i end up? It moves d slots left, wrapping around.

2Hint 2Explore hint

Old index i lands at (i - d + n) % n. Equivalently, new position i should hold the old element at (i + d) % n.

3Hint 3Explore hint

Reduce d %= n first, then fill a result array in a single pass with one of those formulas.

A · Core idea

Compute each element's destination directly and write it into a fresh array in one pass — no repeated shifting.

The one cost. It uses a second array of size n. If the interviewer forbids that, the three-reversal method below achieves the same rotation in place with O(1) extra space.

B · Visual dry run

Interactive dry run

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

a = [1, 2, 3, 4, 5], d = 2

Array state

source

original array; source indices 2,3,4,0,1 feed result 0..4

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

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

C · Code with teaching comments

solution.javaJava

Index Math — Remap Into a New Array (Optimal, O(n) space) — optimal

2 teaching notes

1
public List<Integer> rotateLeft(int d, List<Integer> a) {
2
    int n = a.size();
3
    // Collapse full cycles — rotating by n or a multiple is a no-op.
4
    d %= n;
5
    List<Integer> result = new ArrayList<>(Collections.nCopies(n, 0));
6
    for (int i = 0; i < n; i++) {
7
        // Destination i pulls the old element d slots ahead, wrapping via % n.
8
        result.set(i, a.get((i + d) % n));
9
    }
10
    return result;
11
}

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

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

ComplexityO(n) time, O(n) space — A single pass computing one modular index and one assignment per element → O(n) time. The separate result array of size n → O(n) extra space.

E · Edge cases and pitfalls5a = [1, 2, 3], d = 3 — d %= 3 → 0, so result[i] = a[i] — the original array. Confirms full-cycle reduction.Explore edge cases

Edge cases handled

a = [1, 2, 3], d = 3d %= 3 → 0, so result[i] = a[i] — the original array. Confirms full-cycle reduction.
a = [7], d = 1n = 1, d %= 1 = 0 → unchanged single element. No mod-by-zero because n ≥ 1.

Pitfalls

Skipping d %= n and indexing out of range when d ≥ n.
Mixing the two conventions: result[(i - d + n) % n] = a[i] and result[i] = a[(i + d) % n] are both correct, but blending them scrambles the array.
Right-rotating by using (i - d) when you meant a left rotation's (i + d) for the destination-fill form.

03.3

Approach 3 of 3

Three Reversals — In-Place Rotation (Optimal, O(1) space)

TimeO(n)SpaceO(1)

Bring this out when O(1) extra space is required. Explain why reversing the two halves then the whole array equals a rotation.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Can you rotate without a second array? Think about what reversing sub-ranges does.

2Hint 2Explore hint

Reverse the first d elements, then reverse the remaining n - d elements.

3Hint 3Explore hint

Now reverse the entire array. The two halves swap places and each comes out in the correct order — that's a left rotation by d.

A · Core idea

Rotate in place using three in-bounds reversals, no auxiliary array.

Why O(1) space. Each reversal is a two-pointer swap walking inward, mutating the array directly. No copy is made, so only a couple of index variables are used.

B · Visual dry run

Interactive dry run

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

a = [1, 2, 3, 4, 5], d = 2

Array state

reverse [0,2)

first block reversed

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

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

C · Code with teaching comments

solution.javaJava

Three Reversals — In-Place Rotation (Optimal, O(1) space) — reference

4 teaching notes

1
public List<Integer> rotateLeft(int d, List<Integer> a) {
2
    int n = a.size();
3
    int[] arr = new int[n];
4
    for (int i = 0; i < n; i++) {
5
        arr[i] = a.get(i);
6
    }
7
    // Keep the split point inside the array and skip full cycles.
8
    d %= n;
9
    // Reverse the first block X → Xᴿ.
10
    reverse(arr, 0, d - 1);
11
    // Reverse the second block Y → Yᴿ.
12
    reverse(arr, d, n - 1);
13
    // Reverse everything: (Xᴿ Yᴿ)ᴿ = Y X, the rotated array.
14
    reverse(arr, 0, n - 1);
15
    List<Integer> result = new ArrayList<>(n);
16
    for (int v : arr) {
17
        result.add(v);
18
    }
19
    return result;
20
}
21
 
22
private void reverse(int[] arr, int lo, int hi) {
23
    while (lo < hi) {
24
        int tmp = arr[lo];
25
        arr[lo] = arr[hi];
26
        arr[hi] = tmp;
27
        lo++;
28
        hi--;
29
    }
30
}

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

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

Edge cases handled

a = [1, 2, 3, 4], d = 4d %= 4 → 0. reverse(0,-1) is a no-op, reverse(0,3) then reverse(0,3) cancel → unchanged. Confirms d == n is the identity.
a = [9, 8], d = 1reverse [0,0) no-op, reverse [1,1) no-op, reverse [0,1) swaps → [8, 9]. Minimal rotation works.

Pitfalls

Reversing the wrong sub-ranges or in the wrong order — only X then Y then whole yields a left rotation.
Off-by-one on the reverse bounds: use inclusive [d, n-1], not [d, n].
Forgetting d %= n so reverse(arr, 0, d-1) runs with d ≥ n and goes out of bounds.

Practice

Try the solution yourself

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

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.

Quadratic one-step shifting

Calling a single-rotation routine d times copies every element d times. For d ≈ n that's O(n²) and times out. Compute the final index directly instead.

Explore the code comparison

Don't write this

for (int r = 0; r < d; r++) {
    int first = arr[0];
    for (int i = 1; i < n; i++) arr[i - 1] = arr[i];
    arr[n - 1] = first;
}

Write this instead

d %= n;
for (int i = 0; i < n; i++) {
    result[i] = arr[(i + d) % n];
}

Negative modulo in Java

Java's % returns a negative result for negative operands, so (i - d) % n can be negative and crash. Add n before the mod. (Python's % is already non-negative.)

Explore the code comparison

Don't write this

int dest = (i - d) % n;   // can be negative
result[dest] = arr[i];

Write this instead

int dest = (i - d + n) % n;
result[dest] = arr[i];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Modular index remap + three-reversal in-place rotation

Code pattern to memorize

# new array via index math
result[(i - d) % n] = a[i]   # element at i goes here
# or, fill destination directly:
result[i] = a[(i + d) % n]

# in-place three reversals (left rotate by d):
reverse(a, 0, d - 1)
reverse(a, d, n - 1)
reverse(a, 0, n - 1)

Rules to remember

1Always reduce the shift first: d %= n. A rotation by n (or any multiple) is the identity — skip the work and avoid mod-by-zero style bugs.
2Left rotation: the element at old index i moves to (i - d + n) % n; equivalently new position i pulls from old (i + d) % n. Pick one convention and stay consistent.
3The + n before % n matters in languages where % can go negative (Java) — Python's % is already non-negative.
4The three-reversal trick rotates in place in O(1) extra space: reverse the first d, reverse the rest, reverse everything.
5Left rotate by d and right rotate by n - d are the same operation — a common source of off-by-direction bugs.

Use this pattern when

Cyclically shift / rotate an array or string by a fixed offset
Wrap-around indexing problems ('the next element after the last is the first')
In-place rotation under an O(1) extra-space constraint → reversal trick
Any time you catch yourself shifting elements one at a time in a loop

Choose another pattern when

You only need to *read* rotated values, not materialize them → just index with (i + d) % n on the fly, no copy
Rotation amount changes every query → precompute or use a deque/offset pointer instead of physically moving data
Data is a linked list, not an array → relink nodes instead of index math

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 Array
Right rotation in place — same three-reversal trick with the split at n - k.
Rotate String
Coming soon
Check if one string is a rotation of another via (s + s).contains(goal).
Rotate List
Coming soon
Same idea on a linked list — find the new tail with modular counting and relink.

←

Rotate Array

Continue · Next problem

Sorting: Bubble Sort