In-Place Array Rearrangement

"Do it in place, O(1) extra space" is a classic interview constraint. In-place rearrangement problems test whether you can move elements around with swaps and pointers instead of allocating a second array — a real memory-efficiency skill.

The core idea

Common in-place tools:

• Reversal trick: reversing subranges rotates an array by k in O(n) time, O(1) space (reverse whole, reverse first k, reverse rest).
• Dutch National Flag: three pointers (low, mid, high) sort an array of 0/1/2 in a single O(n) pass.
• Cyclic sort: for values in range [1..n], place each number at index value−1 by swapping — O(n) and O(1), the basis of "find the missing/duplicate number".
• Two-pointer partition: move elements satisfying a predicate to the front.

Problem	Technique	Time	Space
Rotate array by k	reversal trick	O(n)	O(1)
Sort 0s,1s,2s	Dutch flag	O(n)	O(1)
Find missing/duplicate	cyclic sort	O(n)	O(1)
Move zeroes / partition	two pointers	O(n)	O(1)
Next permutation	scan + swap + reverse	O(n)	O(1)

Exam Tricks & Tips

• 🎯 Rotate by k: normalise k %= n first, then triple-reverse — clean O(1) space.
• 🎯 0/1/2 sorting → Dutch National Flag, not count-then-overwrite, when one pass is required.
• 🎯 Numbers in [1..n] with a missing/duplicate → cyclic sort (index = value − 1).
• 🎯 Next Permutation: from the right find first arr[i]<arr[i+1], swap with next-greater to its right, reverse the suffix.
• 🎯 Sign-marking: use the sign of arr[abs(x)−1] as a visited flag to detect duplicates without extra space.
• ❌ Common mistake: forgetting k %= n on rotation, causing out-of-bounds when k ≥ n.

Expected pattern

Rotate, sort 0/1/2, move zeroes, next permutation, or find the missing/duplicate number under an explicit O(1)-space constraint. Interviewers reward swaps-and-pointers over an auxiliary array.

Quick recap

Rearrange with swaps and pointers, not extra memory: reversal trick rotates in O(n)/O(1), Dutch flag sorts 0/1/2 in one pass, cyclic sort places [1..n] values, and sign-marking flags visits. Always O(n) time, O(1) space.

Cover the answer, recall, then check. 11 cards on in-place array rearrangement.

Q1. Rotate an array right by k in O(1) space — method?
A1. Reversal trick: reverse whole array, reverse first k, reverse the rest. O(n)/O(1). Normalise k %= n first.

Q2. Sort an array of 0s, 1s, 2s in one pass?
A2. Dutch National Flag with low/mid/high pointers; swap based on arr[mid]. O(n)/O(1).

Q3. Find the missing number in [1..n] in O(1) space?
A3. Cyclic sort: swap each value to index value−1; the index whose value is wrong reveals the missing number.

Q4. Move all zeroes to the end preserving order?
A4. Two pointers: a write index for non-zeros; O(n)/O(1).

Q5. Next Permutation algorithm?
A5. From the right find first i with arr[i]<arr[i+1]; swap arr[i] with the next-greater element to its right; reverse the suffix after i.

Q6. Why normalise k %= n before rotating?
A6. k can exceed n; without the modulo you rotate too far and index out of bounds.

Q7. Sign-marking trick for duplicates in [1..n]?
A7. Negate arr[abs(x)−1]; if it's already negative, abs(x) is a duplicate — O(n)/O(1), no extra array.

Q8. Dutch flag invariant?
A8. [0..low−1]=0s, [low..mid−1]=1s, [high+1..end]=2s; mid scans the unknown middle region.

Q9. Complexity of reversal-based rotation?
A9. O(n) time (three reversals), O(1) extra space.

Q10. Partition an array around a pivot value in place?
A10. Two pointers / Lomuto swap so all < pivot precede all ≥ pivot. O(n)/O(1).

Q11. Most common in-place bug?
A11. Off-by-one on pointer bounds (Dutch flag high) or forgetting k %= n on rotation.

"Do it in O(1) extra space" is a phrase that appears in half of all array interviews. In-place rearrangement — moving zeros, rotating, partitioning by a pivot, Dutch-flag sorting — shows you can manipulate an array using swaps and pointers rather than a helper array.

Core idea: rearrange elements by swapping within the array itself, guided by pointers, so no proportional extra memory is used. The recurring tools are the two-pointer write index and the reversal trick.

How it works

Beginner — the write-pointer pattern

"Move all zeros to the end, keep order of non-zeros." A slow write pointer marks the next slot for a keeper; a fast read pointer scans:

write = 0
for read in 0..n-1:
    if a[read] != 0:
        swap(a[write], a[read]); write += 1

O(n) time, O(1) space, and stable for the non-zeros.

Intermediate — rotation by reversal

Rotate an array right by k. The elegant O(1)-space method reverses in three steps:

1. Reverse the whole array.
2. Reverse the first k elements.
3. Reverse the remaining n−k.

rotate([1,2,3,4,5], k=2):
reverse all      -> [5,4,3,2,1]
reverse first 2  -> [4,5,3,2,1]
reverse rest     -> [4,5,1,2,3]

Three linear passes → O(n) time, O(1) space. Always take k = k % n first.

Advanced — Dutch National Flag (3-way partition)

Sorting an array of 0s, 1s, 2s (or partitioning around a pivot) in one pass uses three pointers: low, mid, high.

low = mid = 0; high = n-1
while mid <= high:
    if a[mid] == 0: swap(a[low], a[mid]); low++; mid++
    elif a[mid] == 1: mid++
    else: swap(a[mid], a[high]); high--    # do NOT advance mid here

Each element is examined O(1) times → O(n) time, O(1) space. This is also QuickSort's partition core.

Worked example

Sort [2, 0, 2, 1, 1, 0] of 0/1/2 in place. Run Dutch-flag: after the pass the array becomes [0, 0, 1, 1, 2, 2]. Note when we swap a 2 to the back we do not advance mid, because the swapped-in value is unexamined — forgetting that is the classic bug.

When to use it

Whenever the constraint says O(1) extra space or "modify the array in place": move/segregate elements, rotate, reverse, partition, remove duplicates from a sorted array, or cyclic-sort problems ("place value v at index v to find the missing number").

Tricks & gotchas

• After swapping the far element in Dutch-flag, re-examine the same mid — the new arrival is unchecked.
• For rotation, reduce k mod n or you loop needlessly (and reverse-of-reverse cancels out).
• "Find the missing/duplicate in 1..n" is often cyclic sort: put each number at its home index, then scan for the mismatch.
• Mnemonic: "Swap in place, let a write pointer follow."

Worked Example

Problem: Move all zeros to the end of [0, 1, 0, 3, 12] while keeping the order of non-zero elements, using O(1) extra space.

Solution: Use a write pointer w marking where the next non-zero belongs. Scan with read index i; whenever arr[i] is non-zero, place it at position w and advance w.

i	arr[i]	non-zero?	write to w	array so far	w
0	0	no	—	[0,1,0,3,12]	0
1	1	yes	arr[0]=1	[1,1,0,3,12]	1
2	0	no	—	[1,1,0,3,12]	1
3	3	yes	arr[1]=3	[1,3,0,3,12]	2
4	12	yes	arr[2]=12	[1,3,12,3,12]	3

Finally fill positions w..end with zeros → [1, 3, 12, 0, 0].

One pass, in place: O(n) time, O(1) space.

Answer: [1, 3, 12, 0, 0].