Loading…

Module M03 · DSA Curriculum

Arrays & Hashing

The O(1) lookup lever that unlocks ~40% of interview questions.

beginnerPractice Full theoryPrereq:Complexity & Big-O

Start practice Read the theory See all problems

What you'll learn

Choose correctly between array, hash set, and hash map for any given problem
Explain how a hash table achieves O(1) average lookup — and when it degrades to O(n)
Write one-pass O(n) traversals that use a hash map as the "memory"
Apply the two-sum template to any "find two elements that satisfy X" problem
Use frequency counting for anagrams, duplicates, top-K, and majority problems
Apply prefix sums to convert range-sum queries from O(n) to O(1)
Recognise when sorting or two pointers beats hashing (sorted input, or O(1) space required)

When to reach for this

Signals (use it)

"Find two elements that sum to ..." / "Find a pair that ..."
"How many of each?" / "Frequency of ..." / "Most common ..."
"Are these two strings anagrams?" / "Group anagrams"
"Does the array contain duplicates?" / "First unique ..."
"Count subarrays with sum equal to k" → prefix sum + hash map

Anti-signals (don't)

Input is already sorted → two pointers is usually cheaper in space
"No extra space" / "in-place" constraint → hashing is disqualified, sort or two-pointer instead
"Contiguous subarray with a window condition" → probably sliding window
Constraints are tiny (n ≤ 20) → brute force is fine, don't over-engineer

Theory & deep dive

Arrays and hash maps together account for roughly 40% of easy and medium coding-interview problems, and they are the foundation almost every other pattern builds on. An array gives you O(1) access by position; a hash map gives you O(1) access by value. Master the move from one to the other and a huge slice of the interview pool collapses into a single mental model.

The core insight is this: a hash map turns the question "have I seen the value x before?" from an O(n) scan into an O(1) lookup. So a nested-loop O(n²) brute force becomes a single linear O(n) pass. You are trading O(n) extra space for an order-of-magnitude time saving — almost always the right trade in an interview unless you are explicitly told space is constrained.

This module teaches the four levers you will reach for again and again: the one-pass hash map (Two Sum and its cousins), frequency counting (anagrams, top-K, majority), prefix sums (subarray-sum range queries), and set membership (duplicates, uniqueness). Each section gives you the definition, a diagram of how it works, the dual-language template, and the interview talking points.

The big idea in plain words

Imagine a coat-check counter. You hand over your coat (a value) and get a numbered ticket (a key); later you show the ticket and instantly get your coat back without searching the whole rack. A hash map works the same way - it jumps straight to what you stored instead of scanning everything.

That one trick is why so many array problems get fast. Example: to find two numbers in [2, 7, 11, 15] that add up to 9, walk through once and remember each number you have already seen. At 2 you think 'I still need a 7'. When you reach 7 you ask 'have I seen a 7 before?' - yes - so the pair is found in a single walk instead of comparing every possible pair.

Core definitions — the vocabulary

Before the patterns, lock in the vocabulary. Interviewers listen for whether you use these terms precisely.

Term	What it means	Typical cost
Array	Contiguous block of memory indexed by position `0..n-1`.	Access by index O(1); search O(n)
Dynamic array	Auto-resizing array (Java `ArrayList`, Python `list`). Doubles capacity when full.	Append amortised O(1)
Hash set	Unordered collection of unique keys. Answers "is x present?".	Add / contains O(1) average
Hash map	Key → value store. Answers "what is associated with x?".	Put / get O(1) average
Hash function	Maps a key to a bucket index.	O(1) per key
Collision	Two keys hash to the same bucket; resolved by chaining or probing.	Degrades lookup toward O(n)
Load factor	`size / buckets`. When it crosses a threshold the table resizes.	Triggers O(n) rehash

The single most important idea: a hash set tells you *whether* something exists; a hash map tells you *what* is attached to it (an index, a count, a list). Pick the set when existence is all you need — it is lighter and signals intent.

Tip

Java: HashSet / HashMap. Python: set() / dict() — plus collections.Counter for frequencies and collections.defaultdict(int) for "initialise to zero" semantics.

How hashing achieves O(1) — and when it doesn't

A hash table stores keys in an array of buckets. To find a key it runs the key through a hash function to get a bucket index, then looks only inside that bucket — not the whole table. With a good hash function and a low load factor, each bucket holds ~1 item, so lookup is O(1) on average.

The catch: if many keys collide into one bucket, that bucket becomes a linear list and lookups drift toward O(n). This is why interviewers say hashing is O(1) average but O(n) worst case. In practice, for interview inputs you treat it as O(1) — but you should be able to state the worst case if asked.

Note

Hash maps have no inherent order. If a problem needs sorted output or order-by-insertion, you'll sort at the end (O(n log n)) or use a LinkedHashMap / Python dict insertion order.

Choosing the right structure (decision flow)

Most array problems reduce to one decision: what do I need to remember as I scan, and how do I look it up? Walk this flow at the start of any array problem.

This is the question interviewers want to hear you reason through out loud before you write a line of code.

Watch out

If the prompt says "sorted array" or "O(1) extra space", do not default to a hash map — that throws away the property they handed you. Reach for two pointers or binary search instead.

Lever 1 — the one-pass two-sum template

Given an array and a target, find two elements that sum to the target. Brute force is O(n²) nested loops. The one-pass hash map is O(n).

The key reframing: as you iterate, don't ask "does x exist in what I've seen?" — ask "does target - x (the complement) exist in what I've seen?" Store each value's index as you go, and the first time a complement is already present, you've found the pair. This generalises to any "find a pair that together satisfies a property" problem.

Java· Two Sum — one-pass hash map

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seen.containsKey(complement)) {
            return new int[] { seen.get(complement), i };
        }
        seen.put(nums[i], i);
    }
    return new int[0];
}

Tip

Storing the index after checking the complement is what prevents using the same element twice — you only ever match against elements strictly to the left of i.

Lever 2 — frequency counting

When the problem asks "how many of each" or "most/least common", build a frequency map: key → count. In Java that's a HashMap with merge; in Python it's collections.Counter.

Applications: Valid Anagram (two strings share the same frequency map), Top K Frequent, Majority Element, First Unique Character.

Java· Frequency map in Java

Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
    freq.merge(c, 1, Integer::sum);   // count++ with default 0
}

Lever 3 — prefix sums for range queries

When the problem involves "sum of a subarray" or "count subarrays with sum = k", prefix sums plus a hash map are almost always the play.

Define prefix[i] = sum of nums[0..i]. Then the sum of range (i, j] = prefix[j] - prefix[i]. To count subarrays summing to k, ask at each step "how many earlier prefixes equal currentPrefix - k?" and keep those counts in a hash map for O(1) lookup. Seed it with {0: 1} to represent the empty prefix — forgetting this is the classic off-by-one bug.

Python· Subarray sum equals k

def subarray_sum(nums, k):
    count, prefix = 0, 0
    seen = {0: 1}                 # empty prefix has sum 0
    for x in nums:
        prefix += x
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

Variants you'll meet (and the right tool)

Almost every arrays-and-hashing interview question is one of these shapes. Match the prompt to the row and the technique falls out.

Problem shape	Tool	Canonical example
Find a pair summing to a target	Hash map (value → index)	Two Sum
Detect any duplicate	Hash set	Contains Duplicate
Same characters, any order	Frequency map compare	Valid Anagram
Bucket items by a signature	Map (key → list)	Group Anagrams
k most frequent	Counter + heap / bucket sort	Top K Frequent
Count / find subarray by sum	Prefix sum + hash map	Subarray Sum Equals K
Longest run of consecutive ints	Hash set + boundary check	Longest Consecutive Sequence

For Group Anagrams the grouping key is tuple(sorted(s)) in Python (or a 26-length frequency tuple); in Java it's a sorted char[] rebuilt into a String, or an int[26] serialised to a key.

Complexity at a glance

Know these cold — you should be able to state them without thinking.

Operation	Average	Worst case
Hash set / map insert	O(1)	O(n) (all collisions)
Hash set / map lookup	O(1)	O(n)
One-pass scan with hash map	O(n) time, O(n) space	—
Frequency count (fixed alphabet)	O(n) time, O(1) space	—
Group anagrams	O(n·k log k)	— (k = word length)
Sorting fallback	O(n log n) time, O(1)–O(n) space	—

Frequency counting over a fixed alphabet (e.g. lowercase a–z) is O(1) space: the map holds at most 26 entries regardless of input size.

How to talk about this in the interview

“When you open an array problem that needs a relationship between elements, narrate the trade-off before coding: "Brute force is the nested loop at O(n²). I can trade O(n) space for O(n) time by remembering what I've seen in a hash map — specifically, I'll look up the complement rather than rescan. Unless you want constant extra space, I'll go with the hash map." That one sentence earns the algorithm-choice signal interviewers are grading. Then code the one-pass template and close with the explicit complexity statement: O(n) time, O(n) space.”

Common mistakes

–Using a hash set when you need the *index* — use a hash map if the problem returns positions
–Storing the current element before checking its complement, which lets an element pair with itself
–Using `containsKey` + `get` instead of a single `getOrDefault` / `merge` — correct but wordier and slower
–Reaching for hashing when the input is already sorted — two pointers is simpler and O(1) space
–Forgetting to seed the prefix-sum map with `{0: 1}`, which under-counts subarrays starting at index 0
–Claiming hashing is "always O(1)" — say *average* O(1), worst case O(n) under heavy collisions

Complexity summary

One-pass hash-map solutions in this module are O(n) time and O(n) space, where n is the array/string length. Frequency counting over a fixed alphabet is O(n) time and O(1) space. Grouping problems add an O(k log k) factor per element for the sort-based key, where k is the element length.

Practice problems

83 total