When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Sorted input
- Pair constraints
- In-place compaction
When another approach fits better
- Moving a boundary cannot safely discard any candidates
- The answer depends on arbitrary nonlocal history better represented by a map
How it works#
Enumerate every pair or repeatedly shift elements, often costing O(n²).
Identify the ordered fact or write boundary that makes one side disposable.
State what the active interval still contains.
Move exactly the pointer justified by the comparison, including duplicate rules.
InvariantEvery candidate outside the active pointer region has already been resolved or proved unable to improve the answer.
Example and template#
Two Sum II - Input Array Is Sorted
Use sorted order to decide which pointer must move.
Open the full problem brief- Start
L [1, 3, 4, 8] RAll pairs remain inside the interval.
- Sum too large
L [1, 3, 4] RAny pair with 8 and a later-left value is no smaller, so right can move.
left = 0
right = length(input) - 1
while left < right:
observe input[left], input[right]
if condition_met: record_or_return
else if left_side_cannot_help: left += 1
else: right -= 1- Time
- O(n)
- Space
- O(1) extra
- Assumptions
- Each pointer moves monotonically and the input ordering/in-place contract supports the discard rule.
Pitfalls#
Common wrong approaches
A comparison usually proves only one boundary safe to discard.
Without an invariant, the movement can silently skip valid candidates.
Edge cases
- Pointers meeting
- Duplicate values
- Empty and singleton input
- Mutation versus returning a copy
Interview narration
- “The sorted order lets me rule out one boundary at each step.”
- “The answer, if it remains, is inside this interval.”
- “Because the total is too large, only the right boundary is safe to move.”
Practice#
Two Sum II - Input Array Is Sorted
Use sorted order to decide which pointer must move.
Practice this problemRemove a target value from an array in place and return the retained prefix length.
Reveal the pattern decision
Use read/write pointers: the write boundary denotes the next retained position, even though no sorted pair search exists.
Transfer problem
Given sorted timestamps, find whether any two are within an exact target difference.
Checkpoint: Prove how the difference changes when each pointer advances; do not move both on a mismatch.
Follow-up variations
- Skip duplicates while enumerating unique pairs
- Preserve stable order during in-place compaction
Error-log prompts
- What region was unresolved?
- Which fact justified the pointer I moved?