Classic problems with hash maps

Why this matters

Many interview questions about arrays and strings look like they need two nested loops. Compare every pair, or every subarray, and you get O(n squared) work. A hash map often removes one of those loops, because it answers "have I seen the partner of this value?" in constant time. This lesson teaches the four patterns behind most of those questions. Once you can name the pattern, the code is short, and you can explain the complexity clearly.

The patterns are these. The partner lookup finds two values that combine to a target. Frequency counting tallies how often each value appears. Prefix sums with a map count the subarrays that add to a target. The first-index map finds the longest subarray with a property. Each pattern trades memory for speed, and each one stores a small amount of data per value seen.

Before the patterns: why nested loops are slow

Take a list of 10,000 numbers and ask for two that add up to a target. The direct way checks every pair. That is about 10,000 times 9,999 divided by 2, which is roughly 50 million checks. A modern computer can do that in a fraction of a second, but the problem doubles in cost each time the input doubles in size. Double the input to 20,000 and the work becomes four times as large. Interviewers look for the faster idea, because the nested version does not scale.

The fix is to ask what you need for each element. For Two Sum, each number x needs one partner, target - x. If you could check for that partner in constant time, you would not need to look at other numbers. A hash map gives you exactly that check. The rest of this lesson applies the same thinking to other problems.

Pattern 1: Two Sum with a partner lookup

The problem: given numbers and a target, return the positions of two numbers that add up to the target. Each number can be used once, and there is exactly one answer in the simplest version.

The idea: walk through the numbers once. For each number x, the partner you need is target - x. Before you store x, check the map for its partner. The map stores each earlier value with its index. If the partner is there, you are done, and the partner's index is one answer. If not, store x with its index and move on.

Here is the order inside the loop. You check first, then store. If you stored first, a number could find itself as its own partner. With target 6 and the array {3}, storing 3 before checking would match the 3 with itself. Checking first guarantees that the partner came from an earlier index.

Type this into the Input box. The first line holds n and the target, and the second line holds the numbers:

4 9
2 7 11 15

The output is:

0 1

Trace it. The first number is 2, and the partner for 2 is 7. The map is empty, so nothing is found, and the program stores 2 at index 0. The second number is 7, and its partner is 9 - 7 = 2. The map holds 2 at index 0, so the function returns the pair (0, 1). The numbers 2 and 7 add to 9, and the output is their indices.

The function returns an empty vector when no pair exists. The main program checks for that and prints none. A function that returns "no answer" should say so in a way the caller cannot confuse with a real answer. An empty vector works here because a real answer always has two indices.

The complexity is O(n) time and O(n) space. The map can hold every value in the worst case.

Duplicates need one more check. Take the array 3 6 3 with target 6. The value 6 is its own partner only if a second 6 exists, and it does not. The pair that works is the two 3s. Trace it:

• Position 0, value 3. The partner is 3, and the map is empty. Store 3 at index 0.
• Position 1, value 6. The partner is 0, which is not in the map. Store 6 at index 1.
• Position 2, value 3. The partner is 3, which is in the map at index 0. Return 0 2.

The lookup happens before the store, so the map holds only earlier positions. If you stored the current value first, the lookup at position 2 would find that same 3 at index 2, and the program would return 2 2, which is not a pair of two different positions.

Pattern 2: frequency counting

The second pattern counts how often each value appears. The idea is one loop that adds 1 to a counter for each item. The bracket operator creates a missing key with value 0, so freq[c]++ works without a separate check. This one line solves a large family of problems: anagram checks, the most common word, the first value that appears once, and the number of distinct items.

The next program checks whether two words are anagrams. Two words are anagrams when they contain the same letters with the same counts, such as listen and silent. The program builds a frequency map for each word and compares the maps. In C++ two map objects compare equal when they hold the same keys and values. This version uses map on purpose, because comparing two maps is simple. A hash version works too, but it needs the counts compared key by key.

Type this into the Input box:

listen silent

The output is:

anagram

The function letterCounts is the frequency pattern in one loop. The comparison == on the two maps checks every key and every count. If you change one letter in the input, say silent to silenz, the maps differ and the output is not anagram.

Frequency counting has a cost. The map holds one entry per distinct value, so the space is O(k), where k is the number of distinct values. The time is O(n) for the loop, plus the cost of the comparison. For letters, k is at most the alphabet size, so the space is bounded by a constant.

Pattern 3: prefix sums and subarrays that add to K

The third pattern is the most important one for interviews, and it is the hardest to see at first. The problem: count the contiguous parts of an array, called subarrays, whose sum equals k. The values can be negative. A subarray is a run of neighbouring values, such as the second to the fourth.

A prefix sum is the total of everything up to a position. If the array is 1 2 3 -3 3, the prefix sums after each value are 1, 3, 6, 3, 6. Each prefix sum summarises the array up to that point, so the sum of any subarray is the difference of two prefix sums. The subarray from position i to position j sums to the prefix at j minus the prefix at i - 1.

That gives the key fact. A subarray that ends at the current position sums to k exactly when some earlier prefix equals the current prefix minus k. So you keep a map from each prefix value to how many times it has appeared. At each position, you ask how many earlier prefixes equal current - k, and you add that count to the answer.

One detail is easy to forget. The empty prefix, before any value, has sum 0. You must count it from the start. If you do not, every subarray that begins at index 0 is missed. So the map starts with count[0] = 1.

Type this into the Input box:

5 3
1 2 3 -3 3

The output is:

5

Trace the five subarrays that sum to 3. They are 3, 1 2, 1 2 3 -3, 3 -3 3 and 3 at the end. Here is the loop, one value at a time. The table shows the running sum, the value looked up, how many matches it found, and the total.

The table matches the output of 5.

Prefix sums 0, 1, 3, 6, 3, 6 for the array 1 2 3 -3 3, with the lookup and running total after each value

Each row shows one reason a subarray counts. The second row finds the empty prefix, which is why 1 2 is counted. The fourth row finds the empty prefix again, which counts 1 2 3 -3.

The method is O(n) time and O(n) space. It works with negative values, which is why it is the right tool when a sliding window fails. A sliding window needs values that only grow the window's sum, and negative numbers break that rule.

Here is a second example that shows the role of the starting count. For 1 1 1 and k = 2, the answer is 2, because 1 1 appears at two positions. Without the starting count, the loop would print 1. The first pair starts at index 0, so its prefix is 2 and it needs the empty prefix 0 to match. The empty prefix was never stored, so that pair is lost.

Pattern 4: the first index of each prefix

The fourth pattern is a close cousin of the third. Instead of counting subarrays, you look for the longest subarray with a property. The property in this example is that the subarray sums to zero.

The idea uses the same prefix sums. Suppose the prefix sum after position i equals the prefix sum after position j, with i < j. Then the subarray between them sums to zero. The longest such subarray comes from the earliest i and the latest j that share a prefix value. So the map should store the first index where each prefix value appears, and never overwrite it. At each position, if the prefix is already in the map, the length of the subarray from that first index is a candidate for the answer.

Type this into the Input box:

6
3 4 -7 3 1 3

The output is:

4

Watch the index arithmetic, because it causes most of the bugs in this pattern. The prefix after i + 1 values has index i + 1. The map stores that index, not the index of the value. So when the prefix repeats, the length of the subarray is (i + 1) - firstIndex. Here firstIndex is the position of the earlier prefix, and the subarray covers the values between those two prefix positions.

Trace the input 3 4 -7 3 1 3. The prefix sums at positions 0 to 6 are 0, 3, 7, 0, 3, 4, 7. The value 7 appears first at position 2 and again at position 6. The subarray between them covers the values at indices 2 to 5, which are -7 3 1 3. Those four values sum to 0. That is the longest zero-sum subarray in this input, with length 4.

The table below traces the same input one position at a time. The sum column is the prefix after each value, and the last two columns show what the map and the best length do at that step.

Two rows deserve a second look. At position 2 the prefix returns to 0, which matches the empty prefix at index 0, so the first three values sum to zero. At position 5 the prefix returns to 7, which was first seen at index 2, so the values from index 2 to 5 form the longest zero-sum run. The best length is 4, as the program prints.

Notice what the code does not do. It does not overwrite firstAt when a prefix repeats, because it only stores the first occurrence. That is the whole point of the pattern. Overwriting would shorten the answer.

The method is O(n) time and O(n) space, and it also handles negative values correctly. The same structure answers "longest subarray with sum k" when you replace the zero target with prefix minus k.

Pattern 5: count, then scan

The last pattern uses two passes. The first pass counts every value. The second pass looks for a value that meets a condition in the counts. This two-pass structure appears in "first unique character", "first value that appears once" and similar questions.

The reason for two passes is simple. A value can look unique at the start of the sequence, and then repeat later. You cannot decide while reading the first time. You need the full counts before the second pass can answer.

The next program finds the first character of a word that appears exactly once. It counts every character first, then scans the word in order and returns the first character with count 1.

Type this into the Input box:

swiss

The output is:

w

In swiss, the letter s appears three times, w once and i once. The scan visits s first, but its count is 3, so it is skipped. Then it visits w, with count 1. The program prints w and returns. Notice that i also has count 1, but it comes after w in the word, so it is not the first.

The scan must follow the original order. If you looped over the map instead, the answer would depend on the hash order, which you cannot rely on. This is why the loop reads the string, not the map. The lesson 2 rule applies: when order matters, keep the order in your own loop.

The complexity is O(n) time and O(k) space, where k is the number of distinct characters. For letters, k is bounded by the alphabet size.

Worked example: grouping anagrams

A common follow-up question asks you to group words so that all anagrams sit together. The key idea is that two anagrams have the same letters. If you sort the letters of each word, every anagram of that word gives the same string. That string is a shared key, and a map from key to a list of words does the grouping in one pass.

Type this into the Input box:

eat tea tan ate nat bat

The output is:

abt: bat
aet: eat tea ate
ant: tan nat

Work through the keys. The word eat sorts to aet, and so do tea and ate. The word tan sorts to ant, and nat does too. The word bat sorts to abt on its own. The map holds three keys after the loop. It keeps them in sorted order, so the printout is alphabetical by key. Inside each group, the words keep the order in which they arrived: aet holds eat, tea and ate.

The expression groups[key].push_back(word) is the bracket operator used for its intended purpose. The first time a key appears, groups[key] creates an empty vector for it. Then push_back adds the word. The program never checks whether the key exists, because the bracket operator handles that.

The map here is an ordered map, so the output comes out sorted without extra work. A hash version would work too, but its groups would print in hash order, and you would need to sort the keys yourself before printing. That is the lesson from earlier in this module: when the output must be ordered, choose the ordered container or sort first.

The cost is dominated by the sort of each word. For n words of length L, sorting each word costs O(L log L), so the total is O(n L log L) plus the map work. An interviewer may ask for a faster key. Count the 26 letters into an array instead, and build the key from the counts. That costs O(L) per word, and the key is still the same for all anagrams.

Recognising the pattern from the question

Most interview questions name their pattern in the wording. Use this table as a quick check, and say the pattern out loud before you start coding. Naming it shows the interviewer that you have a plan.

If the question matches none of these rows, ask what each element needs to remember about everything before it. Most patterns in this lesson come from that single question. A partner needs a lookup of earlier values. A count needs a tally. A subarray needs the running total. A first occurrence needs the earliest index. Once you can say what must be remembered, the container choice usually follows.

Putting the patterns together

The four patterns cover most of the classic questions, and they often combine. The table summarises when to use each one.

A useful habit is to ask what each element needs from the past. If it needs one partner, use the partner lookup. If it needs a count of everything before, use counting. If it needs the sum of a range, use prefix sums. If it needs the earliest place a value appeared, use the first-index map.

Why the prefix method is fast

It helps to count the work before you choose a method. Take an array of 100,000 values. The nested-loop check of every subarray sums the values of each pair of start and end positions. That is about 100,000 times 100,001 divided by 2, which is roughly 5 billion sums. Even a fast machine spends seconds, and often much longer, on that many sums.

The prefix method makes one pass. For each value, it does one map lookup and one map insert. That is about 200,000 map operations in total, and it finishes almost at once. The table compares the two methods at two sizes.

A map operation costs more than one array access, so the prefix method does not win on every single step. It wins because it removes a whole factor of n. This is the usual trade in algorithm design: pay a constant factor on each step to remove a factor that grows with the input. Interviewers want you to name that trade and to check it with a count like this one.

Edge cases interviewers check

Good answers handle the boundary cases before the interviewer asks. Check each of these before you say your solution is done.

• Empty input. An empty array has no pairs and no subarrays. The Two Sum function returns an empty result, and the subarray count returns 0 because the loop does nothing.
• No answer. When no pair adds to the target, the function should say so clearly. The programs here print none.
• Duplicate values. Two equal values can form a pair with the same target, for example 4 4 for target 8. The partner lookup handles this, as long as you check before storing. With a value that appears twice, the earlier copy is the partner.
• Negative values. Prefix sums handle negative numbers. Sliding windows do not, so prefer the prefix method when negatives can appear.
• Target zero. A subarray that sums to zero is common. The empty prefix at 0 must be counted, as the pattern shows.
• Large sums. The sum of many values can pass the limit of a 32-bit int, which is about 2.1 billion. Use long long for prefix sums and for counts. For example, 300,000 values near 10,000 each sum to 3 billion, which overflows int.

Common mistakes and the bugs they cause

Storing before checking. In Two Sum, this lets a value pair with itself. The output looks plausible, and it is wrong for targets such as 6 with the array 3.

Forgetting the starting count. In the subarray-sum pattern, leaving out count[0] = 1 misses every subarray that starts at index 0. The count is too small, and the bug appears only for certain inputs.

Overwriting the first index. In the longest-subarray pattern, writing firstAt[sum] = i + 1 on every step, instead of only the first time, makes the subarray shorter than it should be. The result is a length that is too small.

Off-by-one on prefixes. A prefix of length i + 1 has index i + 1. Mixing the index of a value with the index of a prefix gives a length that is off by one. Write a small example on paper and check each index.

Using int for sums. The overflow does not crash the program. It wraps to a negative number, and the answer is wrong. Use long long, and test with a large input when the problem allows it.

Relying on map order. A loop over an unordered map gives no order. In the first-unique problem, that gives the wrong answer on some inputs and the right answer on others. Loop over the original sequence.

A debugging walkthrough

Suppose your subarray-sum program returns 3 for the input 1 2 3 -3 3 with k = 3, but the answer is 5. Start by printing the running sum and the count at each step, as the table in this lesson does. Compare each row with what you expect. The first row should look up -2 and find nothing. The second row should find the empty prefix. If the second row finds nothing, the starting count is missing.

Next, check the rows where the lookup finds a repeated prefix. The value 3 appears twice as a prefix, at positions 2 and 4. If your program stores only one occurrence, or it overwrites the count instead of adding to it, the total is too small. The fix is count[sum]++, which adds one each time.

This method, printing one row per step, finds most prefix bugs in a few minutes. Interviewers like to see it, because it shows you can check your own work.

Interview angle

Expect a question like "find two numbers that add to a target" in a first interview. Answer with the partner lookup, state O(n) time and O(n) space, and mention the check-before-store order. Then discuss the sorted alternative: sort the array and use two pointers, which is O(n log n) time and O(1) extra space. The two-pointers visualizer below shows the sorted method. Comparing the two approaches is what interviewers want to hear.

The two-pointer method needs sorted input. It moves one pointer from each end and shrinks the search range. The hash method needs no sorting and keeps the original positions, which the two-pointer method loses when it sorts. That is why the hash version returns indices directly.

For the subarray problem, expect a follow-up about negative numbers. A sliding window works only when every value is positive, because adding a value can only grow the sum. With negative values, the sum can fall as the window grows, so the window cannot shrink safely. Prefix sums with a map handle that case, and the answer is O(n).

For the longest-subarray problem, expect a question about why the map keeps the first index. Explain that the longest subarray needs the earliest matching start and the latest matching end, and that overwriting would throw away the earlier start.

Real uses

These patterns appear in real systems. A payment system checks whether two transactions add up to a refund amount. A log analyser counts events in a time window using prefix counts. A finance tool finds the longest period where the balance stayed at zero, using the first-index pattern. A spell checker counts letter frequencies to decide which words are anagrams of each other. The problems look academic, but the same loops run in production code.

Practice

1. Change the Two Sum program so it returns all pairs that add to the target, instead of the first one. Decide how to handle a value that appears twice.

2. Write a program that counts pairs of values (in any order) with sum equal to a target, using a frequency map. Test with 1 1 1 1 and target 2.

3. Write a function bool hasZeroSumSubarray(const vector<int>& a) that returns true if some non-empty subarray sums to 0. Use prefix sums and a set.

4. Modify the subarray-sum program to count subarrays whose sum is strictly greater than k. Explain why the prefix method does not work for this as easily, and suggest a sorted-prefix method.

5. Find the first repeated character in a string, meaning the first character whose second occurrence is the earliest. Use a set, and explain the difference from the first unique character.

6. Write a program that checks whether a string is a permutation of a palindrome, using a frequency map. Explain which counts must be odd.

7. Predict the output of the first-index program for the input 4 and the values 1 -1 1 -1, and then run it.

8. Explain, in two sentences, why a sliding window fails for subarray sums when values can be negative.

9. Use the subarray-sum table method to trace the input 1 1 1 with k = 2 by hand. Write down each row.

10. Extend the first-unique program so it prints the position as well as the character, counting positions from 0.

11. Write a program that reads an array and prints the length of the longest run of equal values, using one pass and no map.

12. Explain why a set is enough for the first-repeated-character problem but a map is needed for the first-unique-character problem.

What you now know

• A partner lookup turns Two Sum from O(n squared) into O(n). Check for the partner before you store the current value.
• Frequency counting uses freq[x]++, and it solves anagram checks, counts and first-occurrence problems.
• A prefix sum summarises everything up to a position. The number of subarrays with sum k is the count of earlier prefixes equal to the current prefix minus k.
• Start the prefix count with the empty prefix at 0, or you lose every subarray that starts at index 0.
• For the longest subarray with a property, store only the first index of each prefix, and compute the length from the index arithmetic.
• The count-then-scan pattern answers "first value that appears once" in two passes, and it follows the original order.
• Use long long for sums, and handle empty input, no answer, duplicates and negative values before you claim a solution is complete.

The next lesson combines these ideas into a design problem: a cache that uses a hash map and a linked list together, with O(1) operations.