#189 Rotate Array

Mediumsolve on LeetCode ↗

frequently reported atApple Bloomberg Microsoft Samsung Amazon Google

the problem

In plain words

Rotate the array to the right by k steps, in place. The last k elements move to the front.

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

out [5,6,7,1,2,3,4]

in nums = [-1,-100,3,99], k = 2

out [3,99,-1,-100]

1 ≤ n ≤ 10⁵
0 ≤ k ≤ 10⁵
Follow-up: O(1) extra space

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTwo pointers (opposite ends)

Reverse the whole array, and the last k elements are now at the front — but backwards. Reverse those two parts separately and they're back in order.

solutions

From brute force to optimal

Move the last element to the front, shifting everything right, k times.

k %= n.
Repeat k times: save last, shift all right, put last at 0.

timeO(n · k)

Each rotation shifts n elements (k is at most n − 1 after k %= n).

spaceO(1)

One temp variable.

java

1class Solution {2    public void rotate(int[] nums, int k) {3        int n = nums.length;4        k %= n;5        for (int step = 0; step < k; step++) {6            int last = nums[n - 1];7            for (int i = n - 1; i > 0; i--) nums[i] = nums[i - 1]; // shift everything right8            nums[0] = last;9        }10    }11}

Element i belongs at (i + k) % n.

out[(i + k) % n] = nums[i].
Copy out back into nums.

timeO(n)

Two linear passes.

spaceO(n)

The second array.

java

1class Solution {2    public void rotate(int[] nums, int k) {3        int n = nums.length;4        int[] out = new int[n];5        for (int i = 0; i < n; i++) out[(i + k) % n] = nums[i]; // i moves k steps right6        System.arraycopy(out, 0, nums, 0, n);7    }8}

reverse(all), reverse(first k), reverse(rest).

k %= n.
Reverse 0..n−1.
Reverse 0..k−1.
Reverse k..n−1.

timeO(n)

Each element is swapped about twice in total.

spaceO(1)

In-place swaps.

java

1class Solution {2    public void rotate(int[] nums, int k) {3        int n = nums.length;4        k %= n;                       // rotating by n changes nothing5        reverse(nums, 0, n - 1);      // [1,2,3,4,5,6,7] -> [7,6,5,4,3,2,1]6        reverse(nums, 0, k - 1);      // first k          -> [5,6,7,4,3,2,1]7        reverse(nums, k, n - 1);      // the rest         -> [5,6,7,1,2,3,4]8    }9 10    private void reverse(int[] a, int left, int right) {11        while (left < right) {12            int tmp = a[left];13            a[left++] = a[right];14            a[right--] = tmp;15        }16    }17}

in the room

How to say it in the interview

talk track

Start with k %= n and say why — rotating by n is the identity.
Demonstrate the three reversals on [1..7], k = 3; it's convincing in three lines.

traps

Forgetting k %= n: with k > n, reverse(0, k−1) runs off the end.
Rotating left instead of right — check with the example.

what they ask next

Follow-ups

Another O(1)-space method?

Cyclic replacements: follow each cycle i → (i + k) % n, carrying one value; there are gcd(n, k) cycles. Same O(n) time, trickier to get right.

before you submit

Edge cases to test

k = 0, or k a multiple of n → unchanged.
k > n ([1,2], k = 3 → [2,1]).
n = 1 → unchanged for any k.

practise next