Learning Outcome
Recognize sorted pair/triplet problems and explain why moving one pointer safely discards many candidates.
Pattern Recognition
| Item | Detail |
|---|---|
| Core signal | You need a pair, triplet, closest sum, deduped combination, or max width score from an array. |
| Use when | The array can be sorted or the original order is already sorted and each pointer move has a proof. |
| Avoid when | The required invariant is not monotonic or the input constraints point to a simpler direct scan. |
Intuition
After sorting, increasing the left pointer raises the sum and decreasing the right pointer lowers it, so each move removes a whole block of impossible pairs.
Exact Practice Question Names
Two Sum II
- Input Array Is Sorted
- 3Sum
- 4Sum
- 3Sum Closest
- Container With Most Water
- Remove Duplicates from Sorted Array
Interview Approach
- Sort if the problem allows reordering.
- Fix one or two outer indices for triplet or quadruplet variants.
- Move left/right based on the target or score rule.
- Skip duplicates after consuming a valid value.
- Explain the discard proof for the chosen move.
Pseudocode
sort nums
for fixed index i:
left = i + 1
right = n - 1
while left < right:
sum = nums[i] + nums[left] + nums[right]
if sum is target: record answer and skip duplicates
else if sum < target: left += 1
else: right -= 1Sample Dry Run
For [-1,0,1,2,-1,-4], sort to [-4,-1,-1,0,1,2]. Fix -1, then left/right find [-1,-1,2] and [-1,0,1] while duplicate fixed values are skipped.
Edge Cases
- Duplicate values
- All positive or all negative values
- Overflow in 4Sum
- Container width becoming smaller while height may increase
Common Mistakes
- Skipping duplicates before recording the answer
- Using two pointers without sorting when order is not already useful
- Moving both pointers without proving why
Complexity
| Item | Detail |
|---|---|
| Expected time | Usually O(n log n) for sorting plus O(n) for pairs, O(n^2) for 3Sum, O(n^3) for 4Sum. |
| Expected space | O(1) extra apart from output, ignoring sorting implementation details. |
Java, C++ and Python Notes
- Java: prefer explicit classes and clear helper methods over clever one-liners.
- C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
- Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.
Quick Revision Checklist
- Name the pattern before coding.
- State the invariant or DP state in one sentence.
- Dry-run the smallest non-trivial example.
- Close with time and space complexity.