Rearranging Arrays in Place
Move the values, not the array
A playlist holds 100,000 songs, and you want the last three to play first. The obvious way is to move every song one place to the right, with the last one wrapping round to the front, and do that three times. Each step moves every value, so rotating by k costs n · k moves. For k near n that's about n². At the problem's limits, rotating 100,000 values by 99,999 that way is 9,999,900,000 moves, and on the judge it took 0.71 seconds in C++, with the compiler already moving memory as fast as it can.
Nothing needs to move that much. Rotation splits the array into two blocks, the last k values and the rest, and all it does is swap the blocks. There's a tool that swaps blocks without a second array: reversal. Three reversals did the same rotation in 0.09 milliseconds.
This lesson is about rearranging an array where it stands, with O(1) extra space: rotating it, checking whether it was rotated, reading it from the right, and finding the next arrangement of its values.
Rotating with three reversals
Reversing a range is the cheapest rearrangement there is: swap the two ends, step both inward, and stop when they meet. Each value moves once.
Now write the array as two blocks, A B, where B is the last k values. Rotating right by k must give B A. Reversing the whole array gives rev(B) rev(A): the blocks have traded places, which is what you want, but each is backwards. So reverse each block on its own, and it reads forwards again. Reverse all, reverse the first k, reverse the rest:
Rotating [1, 2, 3, 4, 5, 6, 7] right by 3 — The shaded range is the one being reversed; lo and hi are its two ends.
void reverseRange(vector<int>& nums, int lo, int hi) {
while (lo < hi) swap(nums[lo++], nums[hi--]); // swap the two ends, step both inward
}
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k %= n; // rotating by n changes nothing
reverseRange(nums, 0, n - 1); // A B -> rev(B) rev(A): the blocks trade places
reverseRange(nums, 0, k - 1); // rev(B) -> B
reverseRange(nums, k, n - 1); // rev(A) -> A
}
def reverse_range(nums, lo, hi):
while lo < hi: # swap the two ends, step both inward
nums[lo], nums[hi] = nums[hi], nums[lo]
lo, hi = lo + 1, hi - 1
def rotate(nums, k):
n = len(nums)
k %= n # rotating by n changes nothing
reverse_range(nums, 0, n - 1) # A B -> rev(B) rev(A): the blocks trade places
reverse_range(nums, 0, k - 1) # rev(B) -> B
reverse_range(nums, k, n - 1) # rev(A) -> A
static void reverseRange(int[] nums, int lo, int hi) {
while (lo < hi) { // swap the two ends, step both inward
int t = nums[lo];
nums[lo++] = nums[hi];
nums[hi--] = t;
}
}
static void rotate(int[] nums, int k) {
int n = nums.length;
k %= n; // rotating by n changes nothing
reverseRange(nums, 0, n - 1); // A B -> rev(B) rev(A): the blocks trade places
reverseRange(nums, 0, k - 1); // rev(B) -> B
reverseRange(nums, k, n - 1); // rev(A) -> A
}
function reverseRange(nums, lo, hi) {
while (lo < hi) { // swap the two ends, step both inward
[nums[lo], nums[hi]] = [nums[hi], nums[lo]];
lo++;
hi--;
}
}
function rotate(nums, k) {
const n = nums.length;
k %= n; // rotating by n changes nothing
reverseRange(nums, 0, n - 1); // A B -> rev(B) rev(A): the blocks trade places
reverseRange(nums, 0, k - 1); // rev(B) -> B
reverseRange(nums, k, n - 1); // rev(A) -> A
}
Each prints [5, 6, 7, 1, 2, 3, 4], [3, 99, -1, -100], [1, 2, 3], [2, 1], [1] and [5, 6, 7, 1, 2, 3, 4] for [1, 2, 3, 4, 5, 6, 7] with k = 3, [-1, -100, 3, 99] with k = 2, [1, 2, 3] with k = 0, [1, 2] with k = 3, [1] with k = 5 and [1, 2, 3, 4, 5, 6, 7] with k = 10. The step-through made 6 swaps for 7 values: about n swaps in all, so O(n) time, and O(1) extra space.
Two details carry the whole thing. First, k %= n: rotating by n puts every value back where it started, so k = 10 on 7 values is the same as k = 3 (the last case above), and without it the second reversal runs off the end. Second, which block comes first: rotating left by k is the same three reversals in the other order (the first k, then the rest, then everything).
There are two other ways. Copying each value to index (i + k) mod n of a new array is O(n) time but O(n) extra space. Following each value to its new slot in place works too, but the values form gcd(n, k) separate cycles, and tracking them is easy to get wrong. Three reversals are simpler than both.
Was it sorted, then rotated?
Check if Array Is Sorted and Rotated asks whether the array is a non-decreasing array turned some number of places. Picture the values on a circle, with the last one followed by the first. A sorted array, rotated, climbs all the way round except at one spot: the seam, where the largest value is followed by the smallest. So count the drops, the places where the next value is smaller, going round the circle. At most one means yes. If there's at most one, starting just after it the values never fall all the way round, so it really is a sorted array turned.
def check(nums):
n = len(nums)
drops = 0
for i in range(n):
if nums[i] > nums[(i + 1) % n]: # going round: the last value is followed by the first
drops += 1
return drops <= 1 # only the seam of the rotation may drop
It returned True, False, True, True, True and False for [3, 4, 5, 1, 2], [2, 1, 3, 4], [1, 2, 3], [1, 1, 1], [2, 1] and [1, 3, 2]. Equal values never count as a drop, so [1, 1, 1] passes. [2, 1, 3, 4] drops once in the middle and again from 4 round to 2: two seams, so it's no rotation of [1, 2, 3, 4].
Reading from the right
Some questions are about what comes after each value. Read those from the right, and they turn back into the running records of Introduction to Arrays.
Leaders. Array Leaders wants every value that's at least as big as everything to its right. Checking each value against all the ones after it is O(n²). From the right, though, one record does it: the largest value seen so far. A value is a leader exactly when it's at least that big.
def leaders(arr):
found, best = [], -1 # best: the largest value to the right (-1: none yet)
for x in reversed(arr):
if x >= best: # at least as big as everything after it
found.append(x)
best = x
return found[::-1] # found right to left; the problem wants left to right
It returned [17, 5, 2], [7, 7, 3], [3] and [5] for [16, 17, 4, 3, 5, 2], [7, 7, 3], [1, 2, 3] and [5]. The last value is always a leader, and in [7, 7, 3] both 7s are: the first is at least as big as everything after it.
The next permutation. Next Permutation rearranges the array into the next arrangement in dictionary order, the way the arrangements of 1, 2, 3 are listed: 1 2 3 → 1 3 2 → 2 1 3 → 2 3 1 → 3 1 2 → 3 2 1, then back to the first. The trick is to change as little as possible, as far right as possible. Three moves, each with a reason:
- Find the rightmost rise. Walk left while each value is at least the one after it. That tail never rises, so it's already the largest arrangement of its values, and no change inside it can make the array bigger. The first value smaller than its right neighbour, at index i, is the rightmost place that can grow.
- Grow it by as little as possible. Swap nums[i] with the smallest value in the tail that's bigger than it. Because the tail never rises, that's the rightmost bigger value, found by walking in from the end.
- Make the tail as small as possible. After the swap the tail still never rises, so reversing it puts it in increasing order, its smallest arrangement.
If there's no rise at all, the array is the last arrangement (like 3 2 1), and reversing it all gives the first.
The next permutation of [1, 3, 5, 4, 2] — The shaded range is the tail; i marks the rightmost rise and j its swap partner.
Here it is in all four languages, using reverseRange from the rotation above:
void nextPermutation(vector<int>& nums) {
int i = (int)nums.size() - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--; // walk left past the tail that never rises
if (i >= 0) { // nums[i] < nums[i + 1]: the rightmost rise
int j = nums.size() - 1;
while (nums[j] <= nums[i]) j--; // the rightmost bigger value is the smallest bigger one
swap(nums[i], nums[j]);
}
reverseRange(nums, i + 1, nums.size() - 1); // the tail was its largest arrangement: make it its smallest
}
def next_permutation(nums):
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]: # walk left past the tail that never rises
i -= 1
if i >= 0: # nums[i] < nums[i + 1]: the rightmost rise
j = len(nums) - 1
while nums[j] <= nums[i]: # the rightmost bigger value is the smallest bigger one
j -= 1
nums[i], nums[j] = nums[j], nums[i]
reverse_range(nums, i + 1, len(nums) - 1) # the tail was its largest arrangement: make it its smallest
static void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--; // walk left past the tail that never rises
if (i >= 0) { // nums[i] < nums[i + 1]: the rightmost rise
int j = nums.length - 1;
while (nums[j] <= nums[i]) j--; // the rightmost bigger value is the smallest bigger one
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
reverseRange(nums, i + 1, nums.length - 1); // the tail was its largest arrangement: make it its smallest
}
function nextPermutation(nums) {
let i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--; // walk left past the tail that never rises
if (i >= 0) { // nums[i] < nums[i + 1]: the rightmost rise
let j = nums.length - 1;
while (nums[j] <= nums[i]) j--; // the rightmost bigger value is the smallest bigger one
[nums[i], nums[j]] = [nums[j], nums[i]];
}
reverseRange(nums, i + 1, nums.length - 1); // the tail was its largest arrangement: make it its smallest
}
Each prints [1, 3, 2], [1, 2, 3], [1, 5, 1], [1, 4, 2, 3, 5], [5, 1, 5], [3, 1, 2] and [5] for [1, 2, 3], [3, 2, 1], [1, 1, 5], [1, 3, 5, 4, 2], [1, 5, 5], [2, 3, 1] and [5]. Two scans and a reversal: O(n) time, O(1) space. Duplicates are why both scans use >= and <=: [1, 5, 5] becomes [5, 1, 5], and [1, 1, 5] becomes [1, 5, 1].
Sorting the tail instead of reversing it also gives the right answer, but it costs O(n log n) and misses why it works: the tail is already in order, just backwards. For the previous permutation, flip both comparisons: find the rightmost fall, swap with the largest smaller value in the tail, and reverse the tail.
Two write positions
Rearrange Array Elements by Sign has as many positives as negatives and wants them to alternate, starting with a positive, each sign keeping its original order. Positives go to the even slots 0, 2, 4, … and negatives to the odd slots 1, 3, 5, …. So keep one write position for each and move each value straight to its slot in a new array:
def rearrange_array(nums):
out = [0] * len(nums)
pos, neg = 0, 1 # the next free even slot, and the next free odd slot
for x in nums:
if x > 0:
out[pos] = x
pos += 2
else:
out[neg] = x
neg += 2
return out
It returned [3, -2, 1, -5, 2, -4], [1, -1] and [1, -1, 2, -2, 3, -3] for [3, 1, -2, -5, 2, -4], [-1, 1] and [1, 2, 3, -1, -2, -3]. O(n) time and O(n) space, which is what the problem allows.
Doing it in place is tempting: when a slot has the wrong sign, swap in the next value of the right sign. That breaks the order. On [1, 2, 3, -1, -2, -3] it gave [1, -1, 3, -2, 2, -3]: the positives now come 1, 3, 2. A swap carries a value over the ones between, and keeping the order in place needs shifting whole blocks, which is O(n²). When order matters and the problem returns a new array, use one.
Spotting it
Clues that one of these applies:
- "rotate", "shift by k", "in place", "O(1) extra space": three reversals, with
k %= nfirst. - "was it rotated?", "sorted after turning": count the drops around the circle.
- "bigger than everything to its right", or anything about what comes after each value: a record kept from the right.
- "the next arrangement", "the next bigger number with the same digits": the rightmost rise, the smallest bigger swap, the reversed tail.
- "alternate", "interleave", "keep the relative order": one write position per kind.
And the near-misses:
- Rotating a linked list: no indexes, so it's pointer surgery, not reversal: the Linked Lists: From Basics to Advanced section.
- Searching in a rotated sorted array: the order is still mostly there, so binary search adapts; Binary Search Without a Sorted Array covers it.
- The next greater element for every value, not just whether each value leads: a monotonic stack (Stacks & Queues).
- The k-th arrangement, or all of them: stepping k times is too slow; count with factorials, or generate them with backtracking (Recursion & Backtracking).
Common mistakes
Rebinding instead of changing the list, in Python. nums = nums[-k:] + nums[:-k]
That builds a new list and points the local name at it; the caller's list is untouched. After rotate(v, 3), v was still [1, 2, 3, 4, 5, 6, 7]. Assign into the list instead: nums[:] = nums[-k:] + nums[:-k] gave [5, 6, 7, 1, 2, 3, 4].
Forgetting k %= n.
With k = 10 on 7 values, reversing nums[0..k - 1] reaches past the end: IndexError: list index out of range. Reduce k first.
Counting drops without the wrap. for i in range(len(nums) - 1)
[2, 1, 3, 4] returns True: the drop from 4 round to 2 is never seen. Compare the last value with the first too.
A strict comparison in the next permutation's first scan. nums[i] > nums[i + 1]
It stops at an equal pair, which isn't a rise, and then the second scan finds nothing bigger and runs off the front: on [1, 5, 5] it raised IndexError: list index out of range. Walk past equal values with >=.
Swapping with the neighbour instead of the smallest bigger value.
On [1, 3, 2] it gave [3, 2, 1], jumping past [2, 1, 3], [2, 3, 1], [3, 1, 2]. Swap with the rightmost value bigger than nums[i].
> instead of >= for leaders.
[7, 7, 3] returned [7, 3], losing the first 7, which is at least as big as everything after it.
Check yourself
Quiz
1 / 6Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Practice problems
From easier to harder:
- Array Leaders: a record kept from the right.
- Check if Array Is Sorted and Rotated: count the drops around the circle.
- Rotate Array: three reversals, with
k %= n. - Rearrange Array Elements by Sign: one write position per sign.
- Next Permutation: the rightmost rise, the smallest bigger swap, the reversed tail.
Next: Cyclic Sort, where every value has a home slot and swaps put each one there.