Arrays & Hashing

The base of most coding problems: index into arrays in constant time, and use a hash map or set to remember what you have seen so one pass replaces a nested loop.

Overview

An array stores items side by side and finds any one of them by its position in constant time. A hash map (a dictionary) stores key-value pairs and finds a value by its key in constant time on average. Together they turn many brute-force answers that compare every pair, O(n²), into a single pass, O(n).

These problems test whether you can spot the repeated work in a brute-force answer and remove it by remembering what you have already seen. A strong answer names the brute force, says why it is slow, picks what to store in the map, and states the new time and space cost.

What each structure costs

The table is the whole reason the pattern works. A lookup by key in a hash map costs the same as a lookup by index in an array, on average.

Read by index — O(1) — not supported — O(1)
Find a value — O(n) scan — O(1) average — O(log n) binary search
Add at the end — O(1) amortized — O(1) average — O(n) to keep order
Insert or delete a given item — O(n) shift — O(1) average — O(n) shift
Keeps order — insertion order — depends on the language — sorted order

The hash map's O(1) is an average. It assumes the hash function spreads keys well, so few keys share a bucket. With many collisions, one lookup can take O(n). Python's time-complexity notes state both cases for dict and set.

How a hash map finds a key

A hash map is an array of buckets. It turns the key into a number (the hash), maps that number to a bucket index, and then compares keys inside the bucket to find an exact match.

Two rules follow from this picture. First, a key's hash must never change while it is in the map, or the map looks in the wrong bucket. That is why Python refuses a list as a dictionary key: mutable containers are not hashable, while a tuple of hashable items is. Second, two keys that are equal must have equal hashes, which is why you override equals and hashCode together in Java.

When the map fills past a set load factor, it allocates a bigger bucket array and moves every entry. Java's HashMap defaults to a load factor of 0.75. A single resize costs O(n), but spread across all inserts the cost per insert stays O(1) amortized.

The core move: remember what you have seen

Two Sum asks for the indices of two numbers that add up to a target. The brute force checks every pair, O(n²). The better answer walks the array once and asks one question at each number: have I already seen the number that completes the pair?

A trace on nums = [3, 2, 4], target = 6 shows why the order of the check matters. If you stored 3 first and then looked for 6 - 3 = 3, you would pair index 0 with itself.

0 — 3 — 3 — {} — no; store 3 at 0
1 — 2 — 4 — {3: 0} — no; store 2 at 1
2 — 4 — 2 — {3: 0, 2: 1} — yes; return [1, 2]

The cost is one pass, O(n) time, and up to n stored entries, O(n) extra space. Say this trade out loud: the map spends memory to buy speed.

Choosing the key and the value

Most problems in this family differ only in what you store. Decide the key and the value before you write code.

Find a partner for each item — the value — its index — Two Sum
Count things — the item — how many times — Majority Element, Ransom Note
Group things that are equivalent — a canonical form (sorted letters, letter counts) — list of items — Group Anagrams
Test membership only — the value — none (use a set) — Contains Duplicate, Longest Consecutive Sequence
Count subarrays with a given sum — a prefix sum — how many times it occurred — Subarray Sum Equals K
Map one pattern onto another — a character — the character it maps to — Isomorphic Strings, Word Pattern

For grouping, the key must be the same for every member of a group. The sorted letters of 'eat', 'tea' and 'ate' are all 'aet'. A tuple of 26 letter counts also works and avoids the sort. In JavaScript, use a string key: a Map compares array or object keys by reference, so two equal arrays are two different keys.

Prefix sums with a hash map

A prefix sum is the running total up to each position. The sum of any subarray is the difference of two prefix sums. So the question 'how many subarrays sum to k?' becomes 'how many earlier prefix sums equal the current prefix minus k?', which a hash map of counts answers in O(1).

Seed the map with {0: 1}: the empty prefix before the array starts has sum 0, and it lets a subarray that starts at index 0 be counted.

The trace below runs on nums = [1, 2, 1, -1, 2] with k = 2.

1 — 1 — -1 — {0: 1} — 0 — 0
2 — 3 — 1 — {0: 1, 1: 1} — 1 — 1
1 — 4 — 2 — {0: 1, 1: 1, 3: 1} — 0 — 1
-1 — 3 — 1 — {0: 1, 1: 1, 3: 1, 4: 1} — 1 — 2
2 — 5 — 3 — {0: 1, 1: 1, 3: 2, 4: 1} — 2 — 4

The four subarrays are [2], [2, 1, -1], [1, -1, 2] and the last [2]. This method works with negative numbers, where a sliding window does not.

Recognize the pattern

Read the problem for the signal, then pick the tool.

What you will be able to do

Explain why a hash map lookup is O(1) on average and when it degrades to O(n).
Replace a nested loop with one pass and a map, and state the time and space trade.
Pick the key and value for counting, grouping, partner-finding and prefix-sum problems.
Trace Two Sum and Subarray Sum Equals K by hand on a small input.
Choose between hashing and sorting and justify the choice.

When to use it

You need to know in O(1) whether you have seen a value before (Two Sum, Contains Duplicate).
You need how often each item appears (anagrams, Majority Element, Ransom Note).
You need to group items that share a property (Group Anagrams).
You need to remember what came earlier while you walk the array once.
You need sums over ranges or subarrays, including negative numbers (prefix sums).
The brute force compares every pair and the input can be large.

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio