Week 1
Arrays & Hashing
Arrays, hash maps and hash sets, the tools behind almost every interview problem, explained from zero.
- Hash set membership
- Frequency counting
- Hash map lookup
- Grouping by a canonical key
- Bucket sort by frequency
- Prefix and suffix products
- Encoding constraints as set keys
- Find the start of a sequence
Week 1 is about two tools: the array, which keeps things in order, and the hash map (with its little sibling the hash set), which finds things instantly. Almost every problem this week has the same shape: a slow solution that keeps searching an array, and a fast one that remembers what it has seen in a hash map or set. Learn to spot that shape and you’ve learned the week.
An array is a row of boxes, side by side, each holding one value. Every box has a number called its index, which is its position in the row. Indexes start at 0, so in an array of 5 items the indexes are 0, 1, 2, 3 and 4.
- 70
- 31
- 92
- 43
- 64
Inside the computer, memory is one enormous row of numbered boxes, and each box
number is called an address. An array takes a block of boxes that sit next to
each other. So to read item i, the computer doesn’t search: it computes
start address + i × box size and jumps straight there.
That gives an array its two personalities:
- Reading or writing by index is instant:
nums[2]takes one step, whether the array has 5 items or 5 million. - Finding a value is slow: “is 6 in here?” means looking at the boxes one by one, because nothing tells you where 6 is. For n items that’s up to n looks.
In JavaScript an array is an Array; in Python it’s a list. Both can grow.
const nums = [7, 3, 9, 4, 6];nums[2]; // 9 read by index: instantnums[2] = 10; // write by index: instantnums.length; // 5nums.push(8); // add to the end: about one stepnums.includes(6); // true search: looks at boxes one by onenums = [7, 3, 9, 4, 6]nums[2] # 9 read by index: instantnums[2] = 10 # write by index: instantlen(nums) # 5nums.append(8) # add to the end: about one step6 in nums # True search: looks at boxes one by oneA string like "hello" behaves like an array of characters: s[0] is "h"
and s.length / len(s) is 5.
A hash map stores key → value pairs. Think of a dictionary: you look up a word (the key) and get its meaning (the value). Or think of a notebook with a labelled page for every name: to find what you wrote about “dog”, you flip straight to the “dog” page, without reading the pages before it.
look up kiwi: found
| fruit | cents |
|---|---|
| apple | 40 |
| kiwi | 25 |
| pear | 55 |
The trick is a hash function: a small calculation that turns any key into a bucket number. When you store a key, the map computes its bucket and puts the key there. When you look the key up later, it does the same calculation and goes straight to that bucket. No searching.
Two different keys sometimes land in the same bucket. That’s called a collision, and the bucket then holds a short list. Real hash functions spread keys so evenly that buckets almost always hold zero or one key, so we say lookup, insert and delete take O(1) on average: about one step, no matter how many keys there are. (In theory a terrible hash function could put everything in one bucket, but you can ignore that in interviews unless asked.)
A hash set is a hash map with keys but no values. It answers one question fast: “is this in here?”. Use a set when you only care whether you’ve seen something, and a map when you also need to remember something about it (an index, a count, a list).
look up 4: not found
- 7
- 3
- 9
// Hash map: Mapconst price = new Map();price.set("kiwi", 25); // insert or updateprice.get("kiwi"); // 25price.has("plum"); // falseprice.get("plum") ?? 0; // 0 (default when missing)price.delete("kiwi");// Hash set: Setconst seen = new Set();seen.add(7);seen.has(7); // trueseen.size; // 1# Hash map: dictprice = {}price["kiwi"] = 25 # insert or updateprice["kiwi"] # 25"plum" in price # Falseprice.get("plum", 0) # 0 (default when missing)del price["kiwi"]# Hash set: setseen = set() # careful: {} is an empty dict, not a setseen.add(7)7 in seen # Truelen(seen) # 1Big-O notation describes how the amount of work grows as the input grows. It isn’t measured in seconds (that depends on the computer); it counts steps, and only cares about the overall shape. We call the input size n: the length of the array, or of the string.
- O(1) constant: the same work whatever n is. Reading
nums[5], a hash map lookup. - O(log n) logarithmic: each step halves what’s left. Finding a word in a paper dictionary by opening it in the middle.
- O(n) linear: one look at each item. Reading a list once. Double the input, double the work.
- O(n log n) a bit more than linear. Good sorting algorithms.
- O(n²) quadratic: every item against every other item, a loop inside a loop. Double the input, four times the work.
Here’s what that means in actual step counts:
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) |
|---|---|---|---|---|---|
| 10 | 1 | 3 | 10 | 33 | 100 |
| 1,000 | 1 | 10 | 1,000 | 10,000 | 1,000,000 |
| 1,000,000 | 1 | 20 | 1,000,000 | 20,000,000 | 1,000,000,000,000 |
A computer does very roughly 100 million simple steps per second. So for a million items, O(n) is instant, O(n log n) is a blink, and O(n²) takes hours. That’s why interviewers care: the jump from O(n²) to O(n) is the jump from “times out” to “instant”.
Three rules of thumb for reading code:
- Drop the constants. Two separate loops over the array are 2n steps, still O(n).
- Nested loops multiply. A loop over n inside a loop over n is O(n²).
- Space counts too. Extra memory is measured the same way. A hash map that may hold every item is O(n) space; a couple of variables is O(1) space.
This week you’ll see one trade again and again: spend O(n) memory on a hash map to turn O(n²) time into O(n) time.
Have I seen this before? Walk through the items once. For each one, ask a hash set whether it’s already there, then add it. The set replaces “scan everything I’ve passed”, an O(n) search, with a one-step lookup.
Pattern
Hash set membership
Use it when: you need to know whether a value has appeared before, or whether a value exists at all.
Signal words
- “duplicate”
- “appears twice”
- “all unique”
- “already visited”
- “does x exist”
const seen = new Set();for (const x of items) { if (seen.has(x)) { // x appeared before: handle the repeat (often: return) } seen.add(x); // check first, THEN add}seen = set()for x in items: if x in seen: ... # x appeared before: handle the repeat (often: return) seen.add(x) # check first, THEN add- 10
- 21
- 32
- 13
look up 1: found
- 1
- 2
- 3
Used in: Contains Duplicate, Valid Sudoku (one set per row, column and box), Longest Consecutive Sequence (instant “is x here?”).
How many of each? Walk through the items and keep a tally per value in a hash map: value → count. Many problems that look like they’re about order (“is this a rearrangement of that?”) are really about counts.
Pattern
Frequency counting
Use it when: the answer depends on how often values appear, not on their order.
Signal words
- “anagram”
- “same characters”
- “permutation”
- “most frequent”
- “how many times”
- “majority”
When the values are lowercase letters only, there are just 26 possible keys,
so a plain array of 26 counters works too: slot 0 for a, slot 25 for z. The
slot is the letter’s character code minus the code of a.
// Any values: a Mapconst count = new Map();for (const x of items) { count.set(x, (count.get(x) ?? 0) + 1);}// Lowercase letters only: 26 slotsconst letters = new Array(26).fill(0);for (const ch of word) { letters[ch.charCodeAt(0) - 97]++; // 97 = code of 'a'}# Any values: a dictcount = {}for x in items: count[x] = count.get(x, 0) + 1# Lowercase letters only: 26 slotsletters = [0] * 26for ch in word: letters[ord(ch) - ord("a")] += 1| letter | count |
|---|---|
| b | 1 |
| a | 3 |
| n | 2 |
- a30
- b11
- c02
- d03
- e04
- f05
- g06
- h07
- i08
- j09
- k010
- l011
- m012
- n213
- o014
- p015
- q016
- r017
- s018
- t019
- u020
- v021
- w022
- x023
- y024
- z025
Map or array? The array is a little faster and its size never changes, but it only works when you know the alphabet in advance. The map works for anything: numbers, capital letters, emoji.
Used in: Valid Anagram, Group Anagrams (counts as a key), Top K Frequent Elements (the first step).
Is my partner already here, and where? For each item, work out exactly what other value would complete it (its complement), and ask a hash map whether you’ve seen that value. The map remembers something useful about each value you passed, usually its index.
Pattern
Hash map lookup (complement)
Use it when: you need a pair (or partner) that satisfies a condition, and checking every pair would be O(n²).
Signal words
- “two numbers that add up to”
- “find a pair”
- “return their indices”
- “target sum”
- “matching element”
const seen = new Map(); // value -> index where we saw itfor (let i = 0; i < nums.length; i++) { const need = target - nums[i]; // the complement if (seen.has(need)) { return [seen.get(need), i]; } seen.set(nums[i], i); // check first, then remember}seen = {} # value -> index where we saw itfor i, num in enumerate(nums): need = target - num # the complement if need in seen: return [seen[need], i] seen[num] = i # check first, then rememberUsed in: Two Sum. The same “look up what you need” move powers Group Anagrams (look up the group for a key).
Things that belong together get the same label. Compute, for each item, a canonical key: one standard form that’s identical for every item in the same group (like a word’s sorted letters for anagrams). Then a hash map from key → list of items does the grouping in one pass.
Pattern
Grouping by a canonical key
Use it when: items that are 'equivalent' in some way must be collected together.
Signal words
- “group”
- “anagrams of each other”
- “equivalent”
- “same pattern”
- “categorise”
const groups = new Map(); // key -> items with that keyfor (const item of items) { const key = canonical(item); // e.g. [...word].sort().join("") if (!groups.has(key)) groups.set(key, []); groups.get(key).push(item);}return [...groups.values()];groups = {} # key -> items with that keyfor item in items: key = canonical(item) # e.g. "".join(sorted(word)) if key not in groups: groups[key] = [] groups[key].append(item)return list(groups.values())| key | words |
|---|---|
| aet | [eat, tea, ate] |
| ant | [tan, nat] |
| abt | [bat] |
Used in: Group Anagrams.
Use the count as a position. After counting, frequencies are whole numbers between 1 and n. Instead of sorting by frequency (O(n log n)), make n + 1 buckets and drop each value into the bucket whose index is its frequency. Reading the buckets from the top gives the most frequent values first, in O(n). This is how you answer “top K most frequent”.
Pattern
Bucket sort / top K by frequency
Use it when: you need the most (or least) frequent items, and counts are bounded by the input size.
Signal words
- “top k”
- “k most frequent”
- “sort by frequency”
- “most common”
- “better than O(n log n)”
// 1. count (see Frequency counting), then:const buckets = Array.from({ length: nums.length + 1 }, () => []);for (const [value, freq] of count) buckets[freq].push(value);// 2. read from the most frequent endconst result = [];for (let f = buckets.length - 1; f > 0; f--) { for (const value of buckets[f]) { result.push(value); if (result.length === k) return result; }}# 1. count (see Frequency counting), then:buckets = [[] for _ in range(len(nums) + 1)]for value, freq in count.items(): buckets[freq].append(value)# 2. read from the most frequent endresult = []for f in range(len(buckets) - 1, 0, -1): for value in buckets[f]: result.append(value) if len(result) == k: return result- 0
- 31
- 22
- 13
- 4
- 5
- 6
↑ bucket number = how many times
Used in: Top K Frequent Elements.
Carry a running total. A prefix value at position i summarises everything before i (a running sum or product); a suffix value summarises everything after i. One pass from the left and one from the right give every position both summaries, without re-adding or re-multiplying anything.
Pattern
Prefix and suffix (running totals)
Use it when: each position needs information about everything to its left, its right, or both.
Signal words
- “except self”
- “everything to the left”
- “running total”
- “prefix sum”
- “range sum”
- “without division”
const answer = new Array(n).fill(1);let prefix = 1; // everything LEFT of ifor (let i = 0; i < n; i++) { answer[i] = prefix; // use it first... prefix *= nums[i]; // ...then include nums[i]}let suffix = 1; // everything RIGHT of ifor (let i = n - 1; i >= 0; i--) { answer[i] *= suffix; suffix *= nums[i];}answer = [1] * nprefix = 1 # everything LEFT of ifor i in range(n): answer[i] = prefix # use it first... prefix *= nums[i] # ...then include nums[i]suffix = 1 # everything RIGHT of ifor i in range(n - 1, -1, -1): answer[i] *= suffix suffix *= nums[i]- 10
- 21
- 32
- 43
With sums instead of products, the same idea gives prefix sums: store
prefix[i] = sum of the first i numbers once, and the sum of any range
l..r becomes one subtraction, prefix[r + 1] − prefix[l].
Used in: Product of Array Except Self.
Turn every rule into a lookup. When a puzzle has rules like “no repeats in
any row, column or box”, give each rule its own set (or write the rule into the
key: "5 in row 0"). Placing a value means adding facts to sets; a rule is
broken exactly when a fact is already there.
Pattern
Encoding constraints as set keys
Use it when: several 'no repeats within a group' rules must hold at the same time.
Signal words
- “valid sudoku”
- “unique in each row and column”
- “each group must be distinct”
- “N-Queens”
- “already placed”
const seen = new Set();for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { const d = board[r][c]; if (d === ".") continue; const b = Math.floor(r / 3) * 3 + Math.floor(c / 3); for (const key of [`${d} in row ${r}`, `${d} in col ${c}`, `${d} in box ${b}`]) { if (seen.has(key)) return false; // this rule already used d seen.add(key); } }}return true;seen = set()for r in range(9): for c in range(9): d = board[r][c] if d == ".": continue b = (r // 3) * 3 + c // 3 for key in ((d, "row", r), (d, "col", c), (d, "box", b)): if key in seen: return False # this rule already used d seen.add(key)return True| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | 5 | 3 | |
| 1 | 6 | ||
| 2 | 9 | 8 |
- 5 in row 0
- 5 in col 0
- 5 in box 0
Used in: Valid Sudoku.
Only count a run from its first element. Put everything in a hash set. A
value x starts a run exactly when x − 1 is not in the set. Only from those
starts, count upward (x + 1, x + 2, …). Each run is counted once, so the
whole thing is O(n) even though there’s a loop inside a loop.
Pattern
Find the start of a sequence
Use it when: you need runs or chains of related values in unsorted data, faster than sorting.
Signal words
- “consecutive”
- “longest sequence”
- “unsorted”
- “O(n) time”
- “chain”
const set = new Set(nums);let best = 0;for (const x of set) { if (set.has(x - 1)) continue; // not a start let length = 1; while (set.has(x + length)) length++; best = Math.max(best, length);}num_set = set(nums)best = 0for x in num_set: if x - 1 in num_set: continue # not a start length = 1 while x + length in num_set: length += 1 best = max(best, length)- 1
- 2
- 3
- 4
- 100
- 200
Used in: Longest Consecutive Sequence.
Solve them in this order. Each one adds one new idea on top of the last.
- Contains Duplicate (Easy). The purest hash set problem: “have I seen this?”. Get comfortable with
Set/setand with check-then-add. - Valid Anagram (Easy). From “seen or not” to “how many”: frequency counting with a map, then the 26-slot array.
- Two Sum (Easy). A map that remembers where we saw things, plus the complement trick. The most famous interview question there is.
- Group Anagrams (Medium). Reuses Valid Anagram’s insight as a key, and stores lists as map values.
- Top K Frequent Elements (Medium). Counting again, then bucket sort to beat O(n log n).
- Product of Array Except Self (Medium). A change of pace: no hashing, just running products from both ends.
- Valid Sudoku (Medium). Many sets at once, a 2D grid, and the box-index formula.
- Longest Consecutive Sequence (Medium). The hardest reasoning of the week: why a loop inside a loop can still be O(n).
This week's problems
0 of 8 done
Say whether any number appears more than once in an array.
Decide whether two words use exactly the same letters, the same number of times.
Find the two numbers in an array that add up to a target, and return their positions.
Put words that are anagrams of each other into the same group.
Find the k numbers that appear most often in an array.
For every position, multiply all the other numbers together, without using division.
Check that no digit repeats in any row, column or 3×3 box of a partly filled Sudoku board.
Find the length of the longest run of consecutive whole numbers hidden in an unsorted array.