DSA & Implementation · intro
Arrays & Hashing
Hash maps, sets, frequency counting.
Mental model
A hash map trades memory for time: it turns an O(n) scan for "have I seen this?" into an O(1) lookup. Most array problems that feel quadratic collapse to linear once you ask what you would store in a map keyed by value, complement, or frequency.
How to study Arrays & Hashing
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use Hash table (Wikipedia) to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare Arrays & Hashing with Two Pointers. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Two Sum with a hash map, Two Sum, Contains Duplicate and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Common mistakes
- Reaching for nested loops before asking "what would a hash map key on?"
- Mutating a collection while iterating it
- Forgetting hash maps have no order — sort separately if order matters
Learn from primary sources
- Hash table (Wikipedia) (doc)
Practice and explain it back
Two Sum with a hash map
Given an array of integers and a target, return the indices of the two numbers that add to the target. Solve it in a single pass.
Expected evidence: twoSum([2,7,11,15], 9) -> [0,1]
Open the interactive drill →Two Sum
LeetCode #1 — Two Sum. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/two-sum/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Contains Duplicate
LeetCode #217 — Contains Duplicate. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/contains-duplicate/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Product of Array Except Self
LeetCode #238 — Product of Array Except Self. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/product-of-array-except-self/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Group Anagrams
LeetCode #49 — Group Anagrams. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/group-anagrams/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Merge Intervals
LeetCode #56 — Merge Intervals. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/merge-intervals/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Rotting Oranges
LeetCode #1036 — Rotting Oranges. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/rotting-oranges/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Review prompts
- You need to know whether any two numbers in an array sum to a target. What do you key the hash map on, and what does that buy you?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.