Rotate Array

Problem in Plain English

Move each array element k positions to the right, wrapping past the end to the front. Modify the original array; three reversals do this in linear time with constant extra space.

Problem Statement

Given an integer array nums and a non-negative integer k, rotate the array to the right by k steps. A one-step right rotation moves the last element to the front. Update nums itself; the methods shown return no separate result.

A full rotation of n steps restores an array of length n, so only k % n changes the result. Follow-up: can you perform the rotation in place using $O(1)$ extra space?

Constraints

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5

Examples

Example 1

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

One step right gives [7, 1, 2, 3, 4, 5, 6], two steps gives [6, 7, 1, 2, 3, 4, 5], three steps gives [5, 6, 7, 1, 2, 3, 4].

Example 2

Input: nums = [-1, -100, 3, 99], k = 2
Output: [3, 99, -1, -100]

One step right gives [99, -1, -100, 3], two steps gives [3, 99, -1, -100].

Example 3

Input: nums = [1, 2, 3], k = 5
Output: [2, 3, 1]

Three steps form a full cycle, so five steps have the same effect as two. Move the final block [2, 3] before [1].

Example 4

Input: nums = [8], k = 0
Output: [8]

Zero steps leave the array unchanged. With only one position, any allowed k would also leave it unchanged.

Intuition

Cut the array into two blocks: A is the first n - k values and B is the last k, after reducing k by the length. Right rotation changes A followed by B into B followed by A, preserving the order inside each block. In [1, 2, 3, 4, 5, 6, 7] with k = 3, A is [1, 2, 3, 4] and B is [5, 6, 7]; the result is [5, 6, 7, 1, 2, 3, 4]. Modulo arithmetic chooses the destination directly, while reversal moves these blocks without a helper array.

Approaches

Extra Array

Solution Details

Reveal Extra Array: intuition, complexity, and code

Intuition

Copy each original value to its new index (i + k) % n in a helper array, then copy the complete result back. Keeping reads and writes in separate arrays prevents overwriting a value before it has moved, at the cost of linear extra space.

Step-by-Step Logic

Set n = nums.length and reduce k to k % n. In Example 1, n = 7 and k = 3; allocate a zero-filled helper of length n.
For every original index i, compute destination = (i + k) % n and assign helper[destination] = nums[i]. Read only from nums during this pass.
Example 1 places values 1, 2, 3, 4 at indices 3, 4, 5, 6, then wraps 5, 6, 7 to 0, 1, 2.
After all destinations are filled, copy each helper entry back to nums. The original array now holds [5, 6, 7, 1, 2, 3, 4]. Do not merely reassign a local parameter.

Why It Works

A right shift sends index i to (i + k) modulo n. Two different original indices cannot share a destination: if their shifted indices agree modulo n, their original indices agree modulo n, and both are in 0 through n - 1. Every position is therefore filled exactly once. Because reads stay in the unchanged original array until all placements finish, no value is lost; copying back preserves the required original array object.

Dry Run

Extra Array: variable states at each step
Phase	i	Value read	Destination	Helper state	nums state
Initialize	not started	none	none	`[0, 0, 0, 0, 0, 0, 0]`	`[1, 2, 3, 4, 5, 6, 7]`
Place	`0`	`1`	`(0+3)%7 = 3`	`[0, 0, 0, 1, 0, 0, 0]`	unchanged
Place	`1`	`2`	`4`	`[0, 0, 0, 1, 2, 0, 0]`	unchanged
Place	`2`	`3`	`5`	`[0, 0, 0, 1, 2, 3, 0]`	unchanged
Place	`3`	`4`	`6`	`[0, 0, 0, 1, 2, 3, 4]`	unchanged
Place	`4`	`5`	`0`	`[5, 0, 0, 1, 2, 3, 4]`	unchanged
Place	`5`	`6`	`1`	`[5, 6, 0, 1, 2, 3, 4]`	unchanged
Place	`6`	`7`	`2`	`[5, 6, 7, 1, 2, 3, 4]`	unchanged
Copy back	`0`	helper `5`	nums `0`	unchanged	`[5, 2, 3, 4, 5, 6, 7]`
Copy back	`1`	helper `6`	nums `1`	unchanged	`[5, 6, 3, 4, 5, 6, 7]`
Copy back	`2`	helper `7`	nums `2`	unchanged	`[5, 6, 7, 4, 5, 6, 7]`
Copy back	`3`	helper `1`	nums `3`	unchanged	`[5, 6, 7, 1, 5, 6, 7]`
Copy back	`4`	helper `2`	nums `4`	unchanged	`[5, 6, 7, 1, 2, 6, 7]`
Copy back	`5`	helper `3`	nums `5`	unchanged	`[5, 6, 7, 1, 2, 3, 7]`
Copy back	`6`	helper `4`	nums `6`	unchanged	`[5, 6, 7, 1, 2, 3, 4]`

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Let n be the array length. The placement pass and copy-back pass each visit n positions, giving O(n) time even when k is zero. The helper contains n values, so auxiliary space is O(n); writing the final result into nums does not remove this allocation.

Code

Solution.java

1class Solution {2    public void rotate(int[] nums, int k) {3        int n = nums.length;4        k %= n;5        int[] helper = new int[n];6        for (int i = 0; i < n; i++) {7            helper[(i + k) % n] = nums[i];8        }9        for (int i = 0; i < n; i++) {10            nums[i] = helper[i];11        }12    }13}

Hints

Hint 1

Rotating one step at a time shifts every element per step, which is far too slow for 10^5 elements.

Hint 2

A step count at or above the length just repeats full cycles, so reduce it first with k % n.

Hint 3

Reverse everything, then reverse the front k block and the back block separately to fix both orders.

Edge Cases

k = 0 or a multiple of n leaves every value in place. [1, 2, 3] with k = 6 is unchanged.
A larger k wraps around: [1, 2, 3] with k = 5 becomes [2, 3, 1].
A single-element array remains unchanged for any allowed k. Empty arrays are outside the constraints, so n is never zero.
Duplicate values do not need tracking: [2, 2, 1] with k = 1 becomes [1, 2, 2].
Values at signed 32-bit limits move without arithmetic on their values; only indices are added and reduced.

Common Mistakes and Interview Tips

Writing shifted values directly into nums in a single forward pass overwrites unread originals. Use a helper or the reversal method.
Rotating left instead of right changes the destination sign. Right rotation uses (i + k) % n.
Reversal bounds are inclusive: the first block ends at k - 1, and the second starts at k. Normalize k before using it as a boundary.
Assigning nums = helper only changes a local reference in these languages; copy entries into the caller's original array.
Interview tip: the helper approach is already linear. Three reversals improve extra space to O(1); repeatedly shifting one step takes O(nk) before reducing redundant cycles. Explain the two blocks and their restored order.

Key Takeaway

Array rotation is a block reorder. Modulo removes complete cycles, and whole-array plus block reversals exchange two adjacent blocks while preserving order with constant auxiliary space.