In-Place Rearrangement
What is this?
Think of shelving returned books in a library with no trolley. You cannot lay everything out on a table first. The only working space you have is the shelf itself, so every book you move has to displace exactly one other, and you need a rule that guarantees you never lose track of one. That is in-place rearrangement: reordering a collection while standing inside it.
Fun fact: Wiggle Sort's one-pass swap looks too cheap to be correct. It works because the required pattern alternates: when you fix the pair at
(i-1, i), the swap only moves a larger value into a peak slot or a smaller value into a valley slot, so the pair you fixed earlier,(i-2, i-1), stays valid. The proof is short, but it is not obvious until you see it.
🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: every problem here is "reorganise this array with O(1) extra space", and each is solved by naming an invariant that makes overwriting safe: everything before
writeis final, or positioniis settled forever, or slotv-1holdsv.
1. The three moves
Write pointer. Keep two indices over one array: read visits every element, write marks where the next survivor goes. Copy when you keep, skip when you drop. When the scan ends, write is the new length. Nothing is lost, because any slot write overwrites has already been read.
Local swap. Walk the array comparing each element with its neighbour, swapping when the local rule is violated. This is only legal when a single comparison settles a position permanently, because otherwise a later fix undoes an earlier one and you are sorting the hard way.
Scan from the right. For "change it by one swap" problems, the rightmost position you can change is the one that changes the array least. Walk in from the right to the first position that breaks the run you expect (for Previous Permutation, the first arr[i] > arr[i+1]), then pick the best partner to its right.
Array as index. When every value is guaranteed to lie in 1..n, the array has exactly as many slots as legal values. Repeatedly swap each value to the slot it belongs in (v goes to index v-1) and afterwards the first slot holding the wrong value names the missing number.
2. Where you'll actually meet this
- Garbage collectors. Compacting (mark-compact) collectors slide surviving objects toward one end of the heap and leave a boundary pointer behind. That is a write pointer over a much bigger array.
- C++ standard library.
std::removeandstd::remove_ifare the write pointer: they shift the kept elements forward and return the new end, which is why they are paired witherase.std::next_permutationandstd::prev_permutationare the pivot, swap, reverse routine from this chapter. - No spare memory. On a device with a tiny fixed buffer and no allocator, you cannot copy the data to filter it, so the compaction has to happen inside the buffer.
If a problem hands you a bound like 1 <= nums[i] <= nums.length, that is not decoration. It is permission to use the indices as storage.
3. A 30-second worked example (array as index)
nums = [3, 4, -1, 1], and we want the smallest missing positive.
Every value moved to its home at most once, so despite the nested while, the whole thing is O(n).
4. Problems in this chapter
Remove Element
Delete every occurrence of a value and return the count of survivors. The write pointer in its purest form, and the base case for the whole chapter.
Pattern: read/write compaction. Target: O(n) time, O(1) space.
Wiggle Sort
Rearrange so nums[0] <= nums[1] >= nums[2] <= …. One comparison per position, one swap when violated; the greedy is provably enough, and proving that is the real question.
Pattern: local swap with a permanence argument. Target: O(n) time, O(1) space (the obvious sort-then-interleave is O(n log n) time and O(n) space).
Previous Permutation With One Swap
Make the array as large as possible while staying strictly smaller than it was. Scan right-to-left for the first descent, then swap it with the largest smaller value to its right, taking the leftmost of equal candidates, which is the trap.
Pattern: greedy right-to-left scan. Target: O(n) time, O(1) space.
First Missing Positive
Find the smallest absent positive integer in O(1) extra space. Values in 1..n are cycled into their home slots; the first mismatch is the answer.
Pattern: array as its own hash table. Target: O(n) time, O(1) space.
Next Permutation
Rearrange the array into the next lexicographically greater ordering, or into ascending order if it is already the largest. Scan from the right for the first ascent, swap it with the smallest larger value to its right, then reverse the suffix.
Pattern: right-to-left scan, swap, reverse. Target: O(n) time, O(1) space.
5. Common pitfalls
- Swapping with
i++in the cyclic placement. After a swap the new value atistill needs a home. Advance only when the current value is out of range or already correct, or you will silently drop values. - Infinite swap loops on duplicates.
while nums[i] != i+1spins forever when two slots hold the same value; guard withnums[i] != nums[nums[i]-1]. - Returning the array instead of the length. Remove Element wants
write; whatever sits beyond it is explicitly allowed to be garbage. - Taking the rightmost duplicate in Previous Permutation. Among equal candidates the leftmost gives the larger result. It is a one-character bug that passes the sample and fails the hidden test.
- Sorting "just to be safe." Every problem here has an O(n) answer; reaching for
sort()gives up the entire point of the chapter. - Assuming values are in range. Guard the array-as-index trick against negatives and values
> nbefore indexing with them. - Forgetting to reverse the suffix in Next Permutation. After the swap the tail is still in descending order, so reversing it (not sorting it) makes it as small as possible in O(n).
6. Key takeaways
- Name the invariant before you write the loop. "Everything left of
writeis final" is what makes overwriting the input safe. - A write pointer filters in place and returns the new length for free.
- A local swap is only valid if it settles a position forever. If a later pass could undo it, you are sorting, not rearranging.
- For one-swap problems, scan from the right. The rightmost improvable position changes the value the least.
1 <= nums[i] <= nmeans the array can address itself , the highest-leverage constraint to notice in the whole area.- Cyclic placement is linear, not quadratic, because each value reaches its home slot at most once. Be ready to prove it.
Order: Remove Element → Wiggle Sort → Previous Permutation With One Swap → First Missing Positive → Next Permutation.
Core idea: The answer is forced to lie in
[1, n+1], so you only care about values1..n. Use the array as its own hash table: swap each such valuevto its "home" slotv-1. After everything is parked, the first indexiwherea[i] != i+1exposes the gap, and the answer isi+1. No extra space.
Problem, rephrased
A hypervisor allocates virtual-machine handles numbered from 1, and handles freed by dying VMs land back in a tracking buffer in random order. To admit the next VM you need the lowest handle not currently in use. You're given nums, an unsorted integer array holding the buffer's contents. Alongside live handles it can contain anything: negatives, zeros, duplicates, huge stale values.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson