</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

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.

Decision tree: which in-place move fits the problem

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 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 any slot write overwrites has already been read.

Write-pointer walkthrough removing val 3 from [3, 2, 2, 3]

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::remove and std::remove_if are the write pointer: they shift the kept elements forward and return the new end, which is why they are paired with erase. std::next_permutation and std::prev_permutation are 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.

Array-as-index worked example on [3, 4, -1, 1]

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 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. 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 > n before 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

  1. Name the invariant before you write the loop. "Everything left of write is final" is what makes overwriting 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.

Core idea: Keep a slow write pointer marking where the next kept element belongs, and sweep a fast read pointer across the array. Every time the reader lands on a value you want to keep, copy it to the write slot and move the writer forward; skip the write for values you're deleting. The write pointer ends up counting exactly how many elements survived.

Problem, rephrased

A packet processor receives network frames into a fixed-size buffer. You're given an integer array nums, where nums[i] is the code of the i-th frame in the buffer, and an integer val, the sentinel code that an earlier stage stamps on every corrupt frame.

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

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.