Arrays and Hashing for Coding Interviews

Most interview problems start with an array (a Python list, a JavaScript Array), and a surprising number are solved by adding one hash map. Get comfortable with both and you have the first tool to reach for on almost any problem.

An array is a row of numbered lockers. If you know the number, you walk straight to it. If you only know what's inside, you have to open them one by one.

Arrays: fast by position, slow by value

An array stores items side by side in memory, so the computer can jump straight to any position.

Operation	Cost	Why
Read or write `a[i]`	O(1)	Position → memory address is simple arithmetic
Add or remove at the end	O(1) on average	Nothing else moves
Insert or remove at the front or middle	O(n)	Every later item shifts over
Find a value (`x in a`, `a.includes(x)`)	O(n)	It has to look at items one by one

That last row is the important one. If your solution keeps asking "is this value in the array?" inside a loop, you have an O(n²) algorithm hiding in one innocent-looking line.

Finding 18 means checking one by one1 / 4

Is 12 the one? No.

So searching a list is slow... how do I check "have I seen this before?" without looking at everything?

Hash maps and sets: fast by value

A hash map (Python dict, JavaScript Map or object) turns a key into a position using a hash function, so finding a key takes O(1) on average, regardless of how many keys there are. A set (set, Set) is a hash map with keys only.

A hash map works like a coat check: a hash function turns your key into a hook number, so finding it later is one step, not a search.

"Have I seen this?" with a hash map1 / 3

keyindexempty

Looking for two prices that add up to 37. At 12 we need 25: not in the map, so store 12.

Operation	Hash map / set
Insert, look up, delete a key	O(1) average
Visit every key	O(n)
Keep keys in sorted order	Not provided: sort them yourself (O(n log n))

The trade-off is memory: a map of n items costs O(n) extra space. In interviews, trading space for time like this is usually exactly what's wanted, but say it out loud: "this uses O(n) extra memory to get O(n) time."

Tip
In an interview, say the trade-off out loud: "I'm using O(n) extra memory to get O(n) time." Interviewers love hearing that.

Four patterns to recognise

1. "Have I seen this before?" Store items in a set or map as you go, and check each new item against what's stored. Duplicate detection, pair sums and "first repeat" problems all use this.

2. Counting. Count how often each value appears (collections.Counter in Python, a Map in JavaScript). Anagrams, "most frequent", and "can I build this word from these letters?" are counting problems.

3. Grouping by a key. Compute a key for each item and collect items with the same key: words grouped by their sorted letters, orders grouped by customer. The key is the creative part.

python

1def has_duplicate(emails):

2    seen = set()

a set: O(1) lookups

3    for email in emails:

4        if email in seen:

"have I seen this?" in one step

5            return True

6        seen.add(email)

remember it AFTER checking

7    return False

4. Prefix sums. Store running totals so the sum of any stretch a[i..j] is prefix[j+1] - prefix[i], in O(1). Combine with a hash map of earlier prefix sums to answer "how many stretches add up to k?" in one pass.

Prefix sums

	0	1	2	3	4	5
daily	3	4	7	-2	2
prefix	0	3	7	14	12	14

prefix[k] is the total of the first k values. Values 1 to 3 add up to prefix[4] − prefix[1] = 12 − 3 = 9.

Step through: How to approach an array problem

Step 1 of 4

Write the brute force

Usually nested loops. Say its complexity (often O(n²)), so the interviewer knows you have a correct answer to improve.

Python and JavaScript notes

Python's dict and JavaScript's Map both keep insertion order. Don't rely on that in an answer unless you say so.
In JavaScript, plain objects turn every key into a string (obj[1] and obj["1"] are the same key). Use a Map when keys are numbers or arrays.
Neither language can use a list/array as a key directly. Use a tuple in Python, or join to a string (key.join(",")) in JavaScript.
sorted() / .sort() are O(n log n). Sorting first is often a fine plan, but if a hash map gives O(n), the interviewer will ask why you didn't use it.

Common mistakes

Pairing an item with itself in "two items that add up to X" problems: look up before you store.
Forgetting that JavaScript's default .sort() compares as strings: [10, 9, 1].sort() gives [1, 10, 9]. Use .sort((a, b) => a - b).
Modifying a list while looping over it.

Nice work!
You've got the big idea. Try the quick quiz below, then put it to work on the practice problems.