CONCEPT · 75 minutes
Frequency maps, deduplication, and prefix sums — the canonical patterns behind the majority of easy and medium problems. Learn to reach for the right tool before writing a single line of code.
Before I knew these patterns by name, I kept solving the same problems in three different ways and wondering why one approach felt elegant and the others felt like work. The answer was always one of three moves.
Three patterns show up in the large majority of array and string problems: frequency maps, deduplication, and prefix sums. They recur not by coincidence but because they encode the fundamental insight of every array and string problem: the answer usually lives in the relationship between elements, not the elements themselves. A frequency map is a different view of the same data. A prefix sum is a different view of the same data. A set membership check is a question about the relationship between an element and the rest.
Each of these patterns is the same underlying move — spend some memory up front to make a whole class of later questions cheap. That is also why each has a clear failure mode: if you only ask the question once, or if the data keeps changing, the up-front cost may not pay for itself. We will name the when-not alongside the when for each.
Master these three lenses and you will recognise the core structure of a new problem within seconds of reading it.
Pattern recognition in practice: In my orchestration framework, I use frequency maps to track task-state counts (how many running, completed, failed) across a pipeline graph. The same Counter pattern works verbatim in production. These patterns are the vocabulary of the tools you build — not abstract exercises.
A frequency map answers the question: "how many times does each element appear?" It transforms a sequence into a lookup table in a single O(n) pass.
The canonical frequency map problem is the anagram check. Two strings are anagrams if and only if they have identical character frequencies.
The Counter version is cleaner and faster to write. Prefer it unless the problem restricts standard library use (rare).
Group anagrams is a step up: collect all strings that share the same character signature into a bucket. The key insight is to choose a canonical representation that is identical for all anagrams and different for non-anagrams.
Analogy: Think of the canonical key as a filing system. Every anagram of "eat" gets filed under "aet" — sorted alphabetically. You never have to compare two strings directly; you just check which filing cabinet they belong to.
graph LR
A["Input: ['eat','tea','tan','ate','nat','bat']"] --> B["Sort each string\n→ canonical key"]
B --> C["'eat' → 'aet'"]
B --> D["'tea' → 'aet'"]
B --> E["'tan' → 'ant'"]
B --> F["'ate' → 'aet'"]
B --> G["'nat' → 'ant'"]
B --> H["'bat' → 'abt'"]
C --> I["Bucket 'aet':\n['eat','tea','ate']"]
D --> I
F --> I
E --> J["Bucket 'ant':\n['tan','nat']"]
G --> J
H --> K["Bucket 'abt':\n['bat']"]Before reading on: what would you change in group_anagrams if the strings could contain Unicode characters, not just ASCII letters? What would the canonical key be?
Sets answer the question: "have I seen this before?" They give O(1) amortized lookup and O(1) amortized insert, making them the correct tool for any problem involving unique elements or membership tests.
Two Sum is the gateway problem for hash map optimization. The brute force is O(n^2) — compare every pair. The hash map approach is O(n) — for each element, check if its complement already exists.
This "complement lookup" pattern generalises to dozens of problems. Whenever you find yourself writing a nested loop over an array to find two elements that satisfy a condition, ask: can I store one element and look up the other?
Longest Consecutive Sequence is a harder deduplication problem. The sequence must be consecutive — O(n log n) with sorting, O(n) with a set.
Common mistake: Iterating over nums instead of num_set does not change the asymptotic complexity but adds unnecessary duplicate processing. Always iterate over the set when you only care about unique values.
A prefix sum array trades O(n) preprocessing space and time for O(1) range queries. It answers the question: "what is the sum of elements from index i to index j?" without re-scanning the subarray each time.
The prefix array p has length n + 1 where p[i] holds the sum of the first i elements. Range sum [i, j] is then p[j+1] - p[i].
Subarray Sum Equals K combines both tools: prefix sums to represent cumulative totals, and a hash map to answer "how many previous prefix sums equal (current_sum - k)?" in O(1).
Why seen[0] = 1: If the entire subarray from index 0 to i sums to k, then prefix_sum - k = 0. We need that zero to have been "seen" once so the count increments. Missing this initialization is the classic off-by-one in this pattern.
When not to precompute a prefix sum: the prefix array assumes the underlying data is static. If the array is updated between queries, every change forces an O(n) rebuild — and a workload that interleaves updates and range queries can end up slower than the naive re-scan. That is exactly the case a Fenwick tree (binary indexed tree) or segment tree exists to solve, trading O(1) queries for O(log n) queries that survive mutation. Reach for the simple prefix sum only when reads vastly outnumber writes.
Before the quiz, try these from memory:
p, what is the formula for the range sum of nums[2..5]?seen[0] = 1 necessary?Reflective prompt: Frequency maps and prefix sums both transform the original array into a secondary structure that answers a class of questions faster. What are the trade-offs? When is the O(n) space cost not worth paying? Think about an embedded system with 512 bytes of RAM — does the approach change?
If any checkpoint question felt uncertain, re-read that section before taking the quiz. The patterns here appear in the two-pointer and sliding-window module that follows — you will need them there.
Problem: Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest sequence of consecutive integers. Your algorithm must run in O(n) time.
Examples:
[100, 4, 200, 1, 3, 2] → Output: 4 (sequence 1, 2, 3, 4)[0, 3, 7, 2, 5, 8, 4, 6, 0, 1] → Output: 9 (sequence 0..8)The challenge: Sorting would give you O(n log n) — straightforward but too slow. You need O(n), which means no sort allowed. Think about the deduplication pattern.
Hint 1: Convert nums to a set first. This makes "is n in nums?" an O(1) lookup instead of O(n), which is what makes the whole algorithm O(n) overall.
Hint 2: The key insight is "only start counting from sequence heads." A number n is a sequence head if n - 1 is NOT in the set. If you start from every number, you recount — and the algorithm becomes O(n^2) in the worst case.
Hint 3: Once you find a head, extend with while n + length in num_set: length += 1. Each number is visited once as a head and at most once inside a while loop, so total work is O(n).
The trade-off to internalize: We spent O(n) space on a set to buy O(n) time. The sort approach spends O(1) extra space but costs O(n log n) time. For a one-time query on a large array, the set wins. For a tiny embedded system, the sort might be the right call. The decision depends on your constraints — that deliberateness is what separates a good engineer from someone who just memorized the pattern.
Application-level questions on frequency maps, deduplication, and prefix sums
1. You need to check if two strings are anagrams. What is the most efficient approach?
Correct Answer: D
Sorting is correct but O(n log n). Counter comparison is O(n) and preferable. Knowing both approaches and choosing the more efficient one deliberately is the complete answer.
2. The hash-map Two Sum solution is O(n) time. What is its space complexity?
Correct Answer: B
In the worst case (no pair found until the last element), every element is inserted into the hash map, so space is O(n). Compared to the sort + two-pointer approach which is O(1) extra space but requires mutating or copying the input.
3. After building a prefix sum array in O(n), what is the time to answer a single range sum query [i, j]?
Correct Answer: C
prefix[j+1] - prefix[i] gives the range sum in O(1) — two array lookups and a subtraction. The O(n) cost is paid once during build. This trade-off is the whole point of prefix sums.
4. You have an unsorted list of 1 million integers and need to check membership 10,000 times. Which is faster?
Correct Answer: D
list lookup is O(n) each call = 10,000 * O(n). Set build is O(n) once, lookup is O(1) each = O(n) + 10,000 * O(1). bisect approach: O(n log n) sort + 10,000 * O(log n). For 10,000 lookups the set wins on constant factors; bisect is also acceptable but has a log n per query.
5. The 'subarray sum equals k' problem uses prefix sums and a hash map. Why the hash map?
Correct Answer: A
At index i with prefix sum p, we look up (p - k) in the hash map to find how many previous prefix sums exist that would make the subarray [prev+1..i] sum to k. The hash map gives O(1) lookup for each such check, keeping the overall algorithm O(n).