Arrays & Hashing Pattern
Learn when an array scan should carry a set, map, or reusable prefix state—and when another pattern is the better choice.
Recognition cues
Use a set or map when you need to:
- detect a value seen before;
- count, group, or compare frequencies;
- find a complement during one pass;
- reuse prefix information instead of rescanning.
When not to use it
- Contiguous ranges may need a sliding window.
- Sorted input may favor two pointers or binary search.
- Nested choices may need dynamic programming or backtracking.
- Strict O(1) space rules out an auxiliary map unless values are bounded.
Core mental model
Scan once and keep only past information that answers a future question. Before index i, the map or set summarizes exactly the processed prefix; after processing it, the same invariant holds for the next index.
Worked example: Two Sum
Input [2, 7, 11, 15], target 9. Check the complement before storing the current value.
| Index/value | Needed | Seen | Decision |
|---|---|---|---|
| 0 / 2 | 7 | {} | Store 2 → 0 |
| 1 / 7 | 2 | {2: 0} | Found; return [0, 1] |
Invariant: seen contains exactly the values before i, so one item cannot be used twice.
Common failure modes
- Storing before checking and reusing the current item.
- Using a set when the answer needs an index or count.
- Overwriting duplicate information too early.
- Calling O(n) map storage O(1) space.
- Assuming hashing is ordered or worst-case constant time.
Prerequisite order
- One-pass array traversal and indices.
- Set membership and duplicate behavior.
- Map reads, writes, missing keys, and counts.
- Time/space analysis for scans, hashing, and sorting.
Easy → medium → timed check
Solve in order; each step adds one decision to the same prefix-summary model.
Final timed check
Run a 30-minute Arrays & strings mock; state the invariant before coding, then finish with complexity and edge cases.
