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, and the reason it works is a small piece of luck in the definition. Because the required pattern alternates, fixing position i can never break position i-1 — the comparison that settled the previous slot involved a value that only moved further in the right direction. Interviewers love it precisely because the greedy proof is short but not obvious.

🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

---

The one-line 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 write is final, or position i is settled forever, or slot v-1 holds v.

---

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 anything read passes over was destined for deletion anyway.

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 — 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 improve is the one that changes the value least. Find the first place where the sequence descends as you walk leftward, 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

• Log and buffer compaction. Removing expired records from a fixed-size ring buffer is the write pointer, exactly as written above.
• Garbage collectors. Compacting collectors slide surviving objects toward one end of the heap and hand back the boundary pointer — a write pointer over megabytes.
• Databases. VACUUM in Postgres rewrites a page with the dead tuples squeezed out; the shape of the loop is identical.
• Deduplication pipelines. Streaming dedupe with a bounded window keeps survivors compacted at the head of the buffer rather than allocating per batch.
• Embedded systems. Where there is no allocator, in-place is not an optimisation — it is the only thing that compiles.

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, which is the entire question.
Pattern: local swap with a permanence argument. Target: O(n) time, O(1) space (beating the obvious sort-then-interleave).

▶ 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.

---

5. Common pitfalls 🚫

• Swapping with i++ in the cyclic placement. After a swap the new value at i still 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+1 spins forever when two slots hold the same value; guard with nums[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 — 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 > n before indexing with them.
• Next Permutation — rearrange into the next lexicographically greater ordering, in place. What/why: the mirror of Previous Permutation — scan from the right for the first ascent, swap it with the smallest larger value to its right, then reverse the suffix so the tail is as small as possible.

---

6. Key takeaways

1. Name the invariant before you write the loop. "Everything left of write is final" is what makes destroying the input safe.
2. A write pointer filters in place and returns the new length for free.
3. A local swap is only valid if it settles a position forever — if a later pass could undo it, you are sorting, not rearranging.
4. For one-swap problems, scan from the right. The rightmost improvable position changes the value the least.
5. 1 <= nums[i] <= n means the array can address itself — the highest-leverage constraint to notice in the whole area.
6. 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.