Pointers and sliding window · HTML
Maintain candidate pair (l,r), l<r. Compare f(a[l],a[r]) with the target and move one endpoint; every skipped endpoint is proven unable to form an unchecked valid or better pair.
Recognition signals
- The input is sorted and the objective involves a pair.
- The task checks palindrome symmetry or compares both ends.
- When an endpoint combination is too large or small, one movement direction is forced.
- Brute force enumerates O(n²) pairs but sorting enables a linear squeeze.
False friends
| Signal | Why it is different |
|---|
| Unsorted pairing with original indexes | Hashing is often O(n) without sorting; opposite pointers need sorting and index preservation. |
| Contiguous subarray constraint | If frequencies or sums over the full interval matter, use a variable window rather than only endpoint values. |
Core invariant
Every uneliminated pair uses endpoints inside [l,r]; a moved endpoint is proven unable to pair with any remaining opposite endpoint to satisfy the goal.
State, transition, and processing order
| Item | Definition |
|---|
| State | Left pointer l, right pointer r, endpoint values, and an optional best-so-far result. |
| Transition | Compare the endpoint combination; record or return a hit, move l when too small, and r when too large, as justified by monotonicity. |
| Frontier / order | A staircase boundary in the two-dimensional pair matrix, compressed into two one-dimensional pointers. |
Python skeleton
def pair_with_sum(sorted_values, target):
left, right = 0, len(sorted_values) - 1
while left < right:
total = sorted_values[left] + sorted_values[right]
if total == target:
return left, right
if total < target:
left += 1
else:
right -= 1
return None
Correctness sketch
- If the sum is too small, the smallest endpoint paired with anything no larger than right cannot do better, so left is safely excluded.
- If the sum is too large, the symmetric argument excludes right.
- Each move preserves every possible solution and strictly shrinks the interval; a hit is valid and exhaustion proves absence.
Complexity
| Time | Space | Parameters |
|---|
| O(n), or O(n log n) when sorting is required | O(1), excluding a sorted copy or index map | n is the item count; each pointer moves at most n times. |
Edge cases
- Fewer than two items provide no pair.
- Duplicate values may form a valid pair but must use distinct indexes.
- To enumerate all pairs, skip duplicates or count them according to the output contract.
- Fixed-width languages may need a wider type for endpoint sums.
Error patterns
| Pattern | Why it fails / fix |
|---|
| No elimination proof | Moving the pointer that merely feels right can skip a solution. |
| Using left<=right | That can pair an element with itself; ordinary two-item problems use left<right. |
| Losing original indexes | When output needs original positions, sort (value,index) records. |
Selection and exclusion rules
- For a relationship between two items in sorted data, try an inward squeeze first.
- For existence in unsorted data with original order, hashing may be more direct.
- When the whole interval's aggregate matters, switch to sliding window.
Original micro-example
| Part | Detail |
|---|
| Result | The selected endpoint values are 1 and 9. |
| Setup | Sorted values [1,4,6,9,13], target sum 10. |
| Trace | 1+13 is too large, so decrease the right endpoint to 9; 1+9 matches. |
Recall prompts
My notes