1Understand
The idea
A fast pointer reads every element; a slow pointer marks where the next kept element should be written. Everything before the slow pointer is the finished result. This filters, deduplicates or partitions an array in place in one pass with O(1) extra space.
Intuition
A fast pointer reads every element; a slow pointer marks where the next kept element should be written. Everything before the slow pointer is the finished result. This filters, deduplicates or partitions in place in one pass with O(1) extra space.
The invariant is the whole story: after each step, a[:write] is the answer so far. Partition problems (Dutch flag, move zeros) use the same idea with more boundary indices.
When merging two sorted arrays into one buffer. Write from the back so you do not overwrite unread values.
What you will be able to do
- Maintain a read/write invariant
- Partition arrays in place
When to use it
- Remove or move elements in place
- Return the new length
- O(1) extra space required
2See it
Walkthrough
Remove zeros in place
nums = [0, 1, 0, 3, 2], slow writes kept values; fast reads everything.
1 / 7
slow marks the next write slot. fast = 0 sees 0 → skip (do not write).
Live template
Line 1 active
Complexity: time O(n), space O(1)
Time O(n), extra space O(1). Building a new list is simpler but fails "in-place" constraints. For 3-way partition, three indices keep the same linear bound. Merging from the front into a shared buffer is the classic overwrite bug.
Read the walkthrough as text
Remove duplicates from sorted array. a = [0,0,1,1,1,2,2].
write = 1(first element always kept).readscans from 1..n-1; whenevera[read] != a[write-1], copy toa[write]and advancewrite.- End state:
a[:write] = [0,1,2], returnwrite == 3.
In code:
write = 1for read in range(1, len(a)):if a[read] != a[write - 1]:a[write] = a[read]write += 1
3Recognise it
Kinds of problems (7)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Remove elements in place
Example. Remove all instances of val; return new length.
How. Write pointer only advances when nums[read] should be kept; overwrite in place.
Remove duplicates from sorted array
Example. In-place unique count for a sorted array.
How. Write position 0 fixed; copy nums[read] when read > 0 and different from last written.
Move zeroes
Example. Push all zeros to the end while keeping relative order of nonzeros.
How. Same read/write: swap or assign nonzeros to write index, then fill tail with zero.
Dutch national flag (3-way partition)
Example. Sort array of 0, 1, 2 in one pass.
How. Three pointers: mid scans, low swaps 0s, high swaps 2s.
Merge sorted arrays from the back
Example. Merge into nums1 with extra space at the end.
How. Write pointer at the end; pick larger from A[i], B[j] and move backward to avoid overwrite.
Subsequence check across two sequences
Example. Is s a subsequence of t?
How. Advance read on t when it matches s[write]; success when write reaches len(s).
Resolve forces from both sides (dominoes)
Example. Simulate domino push left/right on a string.
How. Two scans from ends with force counters; R and L meet with the stronger force winning.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Extra array
Why it happens. Building a new list is easier than maintaining the write invariant.
How it fails. Remove duplicates by appending to `out`, works logically but fails “in-place O(1) space”.
Fix. Keep write index; overwrite nums[write] and return write length.
Broken invariant
Why it happens. The write pointer advances when the element should be skipped (or vice versa).
How it fails. Remove val: you advance write on every element including matches, duplicates remain.
Fix. Only write when `keep(x)`; read always advances. Write only on kept elements.
Forward overwrite
Why it happens. Merging from the front overwrites unread tail of the longer array.
How it fails. Merge in place from index 0: first written value clobbers an element you still need to read.
Fix. Merge from the end (backward write index) or use extra buffer when merging forward.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.