Foundation · Module 6 · Lesson 2
Same-direction pointers
Read/write indexes for in-place compaction.
Lesson 33 of 123
1d streakSame-Direction Pointers: Reader and Writer (Fast & Slow)
Same-direction pointers (also called reader-writer pointers) traverse a sequence in the same direction at varying rates. The fast pointer scans ahead inspecting values, while the slow pointer marks the boundary of the modified, in-place valid prefix.
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int write = 1;
for (int read = 1; read < nums.length; read++) {
if (nums[read] != nums[read - 1]) {
nums[write++] = nums[read];
}
}
return write;
}Active Recall Checkpoint
What invariant is preserved by nums[0..write-1] during array deduplication?
Show answer & explanation
At every step, nums[0..write-1] contains the sorted prefix of unique elements seen so far with zero duplicates.
Use it when
Use reader-writer pointers for in-place array transformations: removing duplicates, moving zeroes, and in-place partitioning.
Reconsider when
Reconsider when original indices must be retained or when creating a new array is allowed and avoids in-place state mutation.
Cost Model
Complexity & Trade-offs
When to use it
- Sorted pair search, compaction, merging, partitioning, and palindrome checks.
- Replacing nested loops when boundaries move monotonically.
- Maintaining disjoint processed and candidate regions.
Common mistakes
- Moving a pointer without proving the discarded region is impossible.
- Forgetting duplicate skipping in enumeration problems.
- Applying an order-dependent pointer rule to unsorted data.
Practice prompts
- Reproduce the worked Same-direction pointers example without looking at the trace.
- Change one input condition and explain whether the Same-direction pointers invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check