Core Patterns
Hash maps & frequency
Lesson 2 of 5
What you'll learn
- Use a Map for constant-time lookups instead of repeated scans
- Build frequency tables to count, group, and dedupe
- Trade memory for time by remembering what you have already seen
If you only internalize one structure for interviews, make it the hash map. In JavaScript that is Map (or a plain object for string keys). Its superpower is constant-time get, set, and has, which lets you answer "have I seen this before?" without rescanning the data. Most "make it order n" insights amount to: remember the past in a map so the future is a lookup instead of a search.
// frequency table: count occurrences in one pass
function counts(arr) {
const freq = new Map();
for (const x of arr) {
freq.set(x, (freq.get(x) ?? 0) + 1);
}
return freq;
}
counts(["a", "b", "a", "c", "a"]); // Map { a => 3, b => 1, c => 1 }
Counting, dedupe, and grouping
Three patterns cover most uses. Counting builds a frequency table, as above, and answers questions like "first non-repeating element" or "most common value." Dedupe uses a Set to keep only first occurrences. Grouping maps a derived key to a bucket array, which is how you group anagrams or partition records by some field. All three are one pass, order n time, order n space.
The complement trick
The deepest hash-map idea is storing complements. Instead of asking "is there a pair that sums to the target?" by checking every pair, you ask, for each number, "have I already seen the value that would complete it?" You store each number as you go, so the answer is a single lookup. That converts an order n squared double loop into a single order n pass, and it is exactly how two-sum works.
Map versus plain object
Use a Map when keys may be numbers, booleans, or objects, when you need reliable insertion order, or when you care about size. Reach for a plain object only for simple string keys where the ergonomics are nicer. Map keys never collide with inherited prototype names.
The challenge implements two-sum in one pass: for each number, it checks the map for the complement before storing the current value.
Run it. For each number, look up the complement that would reach the target, then store the current value for later numbers.
How does the one-pass two-sum approach avoid checking every pair of numbers?
Next: two pointers and sliding windows for arrays and strings.
Saved on this device. Sign in to sync your progress everywhere.