02
Same direction (read / write) (Two Pointers Sub-pattern)
Both pointers walk left to right. read looks at every element; write is where the next element you keep goes.
Signals in the problem statement
- ›
"in place", "O(1) extra space"
- ›
"remove", "deduplicate", "move zeros"
- ›
"return the new length"
- ›
walking two sequences together
What makes it different
There's no comparison between the two pointers — write simply trails behind read. The only decision is the keep rule. When the rule looks at earlier elements (duplicates), compare with the written part (nums[write − 1], or nums[write − k] for “at most k”), never the read part — those cells may already be overwritten.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Remove ElementWalkthroughEasyBasic Anchor·LeetCode #27
- 2Remove Duplicates from Sorted ArrayWalkthroughEasyBasic Reinforcement·LeetCode #26
- 3Move ZeroesWalkthroughEasySlight Variation·LeetCode #283
- 4Remove Duplicates from Sorted Array IIWalkthroughMediumMedium·LeetCode #80
- 5Is SubsequenceWalkthroughEasyPattern Transfer·LeetCode #392
Template
read-write-template.cpp
// Same direction (read / write): keep only the elements you want, in place.
// Everything before `write` is the final answer so far.
int keepIf(vector<int>& a, int removeValue) {
int write = 0;
for (int read = 0; read < (int)a.size(); read++) {
if (a[read] != removeValue) { // the "keep" rule changes per problem
a[write] = a[read];
write++;
}
}
return write; // new length: a[0 .. write-1]
}Remember this · Two Pointers
Trigger
Sorted array, pairs/triplets with a target, comparing from both ends, compacting an array in place.
Think
If I compare the elements at two positions, can I safely discard one side?
Key question
Which pointer moves, and why can the skipped elements never be the answer?