Rotate Array

MediumArrays · Reversal Trick🧩 Array Manipulation LeetCode #189 ↗Updated Oct 30, 2026

Problem

Shift the elements of nums to the right by k positions, in-place. Elements pushed off the end wrap around to the front, so after the rotation the value at index i ends up at index (i + k) % n. Note k may be larger than the array length.

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

Inputnums = [-1,-100,3,99], k = 2Output[3,99,-1,-100]

Inputnums = [1,2], k = 5Output[2,1] (5 % 2 = 1)

1 ≤ n ≤ 10⁵ · -2³¹ ≤ nums[i] ≤ 2³¹-1 · 0 ≤ k ≤ 10⁵ · Follow-up: O(1) extra space.

Try it yourself

Java

class Solution {
    public void rotate(int[] nums, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A right rotation by k moves the last k items to the front with both blocks keeping their order. Reverse the whole array, then reverse each block back: the blocks swap places and each is restored.

PatternArray Manipulation

Instinct "In place", "O(1) extra space" or "one pass" over an array? Think write pointer, reversal, prefix/suffix passes or using indices as storage.

Memory hack Read fast, write slow, reverse to rotate, and let the index be the hash.

Open the Array Manipulation guide →

Approaches

Brute ForceRotate One Step, k Times

Time O(n·k)Space O(1)

A single right rotation saves the last element, shifts everything one slot right and drops the saved value at index 0. Repeat it k % n times (a full lap of n steps changes nothing).

Java

public void rotate(int[] nums, int k) {
    int n = nums.length;
    k %= n; // n rotations is a no-op
    for (int step = 0; step < k; step++) {
        int last = nums[n - 1];
        for (int i = n - 1; i > 0; i--) {
            nums[i] = nums[i - 1];
        }
        nums[0] = last;
    }
}

Simplest in-place idea, but up to 10¹⁰ moves at the limits.

BetterPlace Each Element via a Copy

Time O(n)Space O(n)

We know every element's destination: index i goes to (i + k) % n. Write each value into a fresh array at its target, then copy the result back into nums.

Java

public void rotate(int[] nums, int k) {
    int n = nums.length;
    int[] rotated = new int[n];
    for (int i = 0; i < n; i++) {
        rotated[(i + k) % n] = nums[i];
    }
    System.arraycopy(rotated, 0, nums, 0, n);
}

Linear and easy to get right, but needs an O(n) copy.

OptimalThree Reversals

Time O(n)Space O(1)

Write the array as A·B where B is the last k items; we want B·A. Reversing everything gives rev(B)·rev(A); reversing each part again restores the inner order, leaving B·A. Every element is swapped about twice.

Java

public void rotate(int[] nums, int k) {
    int n = nums.length;
    k %= n;
    reverse(nums, 0, n - 1); // A B -> rev(B) rev(A)
    reverse(nums, 0, k - 1); // restore B
    reverse(nums, k, n - 1); // restore A
}

private void reverse(int[] nums, int lo, int hi) {
    while (lo < hi) {
        int tmp = nums[lo];
        nums[lo++] = nums[hi];
        nums[hi--] = tmp;
    }
}

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

B last k blockA first n-k block changed

start
1
A
2

3

4

5
B
6

7

k=3: A=1..4, B=5..7
rev all
7
B
6

5

4
A
3

2

1

blocks swapped, reversed
rev 0..2
5
B
6

7

4

3

2

1

B back in order
rev 3..6
5

6

7

1
A
2

3

4

A back in order ✔

Linear, in-place and short — answers the follow-up.

Pro tip

Always reduce k %= n first; otherwise reverse(0, k-1) runs past the end when k > n.

At a glance

Level	Approach	Time	Space
Brute Force	Rotate One Step, k Times	`O(n·k)`	`O(1)`
Better	Place Each Element via a Copy	`O(n)`	`O(n)`
Optimal	Three Reversals	`O(n)`	`O(1)`

Common pitfalls

Skipping k %= n — out-of-bounds reversals or wasted full laps.
Rotating left instead of right: the last k elements must come to the front.
Assigning nums = rotated in Java — that rebinds the local reference; the caller's array is unchanged.

Interview tips

Write out A·B → B·A on the board; the reversal proof is then one line.
Mention cyclic replacements (follow each element's chain, gcd(n,k) cycles) as another O(1)-space option.
Test k = 0, k = n and k > n explicitly.

Pattern

Reversal trick → swap two adjacent blocks of an array (or words in a string) in-place.

My notes saved in this browser