167: DSA - Hashing, Two Pointers, and Sliding Windows
Learning outcomes
- recognize frequency-map and membership problems;
- maintain a two-pointer or window invariant;
- handle empty input, duplicates, and boundary movement.
Practice
Implement pair sum, longest unique substring, and minimum-size subarray problems. For each, write brute force first, then the optimized solution, complexity, invariant, and three edge-case tests.
Lesson and worked examples
For pair sum, scan left to right and keep needed = target - value in a map. On [2, 7, 11, 2], target 9, store 2 at index 0, then find 7's complement and return [0, 1]; never reuse the current item. For longest unique substring, keep a window and the last index of each character. When s[right] is inside the window, set left to last + 1, never backwards. For "abba", window lengths progress 1, 2, 2, 2.
The classic minimum-size positive-sum window works because adding at the right and removing at the left are monotonic. Expand until the sum reaches the target, record length, then shrink. Negative values break that proof: use prefix sums plus a monotonic deque for the shortest subarray with sum at least k, or explicitly retain the constraints that permit a normal window.
Deliverable
For each problem submit a brute-force oracle, optimized implementation, invariant, and complexity. State whether indices or values are returned, how ties are resolved, and whether Unicode is code points or UTF-16 units.
Tests and rubric
Include empty input, one item, duplicate values, same-element reuse, no answer, target zero, all-positive and negative values, repeated characters, Unicode if in scope, and a window covering the whole array. Score 3 points each for constraint-based pattern choice, invariant, correctness, complexity, and test quality. A sliding-window solution without a positivity explanation cannot receive full credit.
Checkpoint
Explain when a sliding window can move its left pointer permanently forward and when negative values invalidate that reasoning.
Invariant notebook
For longest-unique-substring, maintain a window whose characters are unique. Expand the right edge, remove from the left until the invariant returns, then record the valid length. The left edge never moves backward, so the two pointers together make O(n) visits. For a sum constraint with negative numbers, that monotonic shrink argument no longer holds; choose prefix sums or another method instead.
Tests
Include an empty array, one item, repeated values, a match using the same element twice, Unicode strings if strings are in scope, and a target that has no answer.