Two-sum and frequency maps

Why this matters

A bank statement lists many payments. You want to know whether two of them add up to a refund of 150. A poll collects many votes, and you want to know which option got the most. A log holds many error codes, and you want to know how often each one appears. Each question asks about the values in a list, not about their positions.

A direct approach works for a short list. You compare every pair of items. For a list of 10,000 numbers there are about 50 million pairs, so this approach takes about 50 million comparisons. A map lets you answer the same questions while reading the list once. For 10,000 numbers that is about 10,000 lookups.

This lesson uses one kind of map for two jobs. A frequency map counts how many times each value appears. A two-sum search finds two values whose sum is a target. Both jobs use a hash map, which is a container that finds a key in about one step on average. The hash collisions lesson in this module explains how the container does that. Here you only need its behaviour: give it a key, and it tells you the stored value quickly.

Each section shows the Java version and the C++ version side by side, so you can see that the idea is the same in both languages.

A frequency map is a tally sheet

Picture a tally sheet on a table. Every time you see a word, you draw one mark next to that word. At the end, you count the marks. The word with the most marks is the most common one. A frequency map is that tally sheet in code. The key is the value you are counting, and the stored number is the count.

Take the words apple, pear, apple, fig, pear and apple, read in that order:

1. apple is new, so its count starts at 1.
2. pear is new, so its count starts at 1.
3. apple is already there, so its count goes from 1 to 2.
4. fig is new, so its count starts at 1.
5. pear is already there, so its count goes from 1 to 2.
6. apple is already there, so its count goes from 2 to 3.

At the end the tally says apple 3, pear 2 and fig 1. The program reads the list once, and each word costs one lookup and one update.

Worked example 1: counting words

The Java version uses HashMap, the standard hash map in Java. The method merge does the tally in one call. It takes a key, a value to add when the key is new, and a rule for combining the old and new values. Integer::sum is a short name for the function that adds two integers. So merge(w, 1, Integer::sum) means: if w is new, store 1, and if it is already there, add 1 to the stored count.

import java.util.HashMap;
import java.util.Map;
 
public class Main {
    public static void main(String[] args) {
        String[] words = {"apple", "pear", "apple", "fig", "pear", "apple"};
 
        Map<String, Integer> freq = new HashMap<>();
        for (String w : words) {
            freq.merge(w, 1, Integer::sum);
        }
 
        for (String w : words) {
            System.out.println(w + ": " + freq.get(w));
        }
 
        System.out.println("kiwi appears " + freq.getOrDefault("kiwi", 0) + " times");
        System.out.println("distinct words: " + freq.size());
    }
}

Output:

apple: 3
pear: 2
apple: 3
fig: 1
pear: 2
apple: 3
kiwi appears 0 times
distinct words: 3

The loop that prints the counts walks the original list, not the map. That keeps the output in the same order as the input, which makes the result easy to check. The method getOrDefault returns the count, or 0 when the key is missing. Use it when a missing key is a normal answer. Using get for a missing key returns null, which causes trouble in Java, as the mistakes section shows.

The C++ version uses map, which keeps its keys sorted. The bracket operator freq[w] finds the key w, and if the key is missing it creates the key with the value 0 first. The ++ then adds one. So ++freq[w] is the C++ tally mark.

#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
 
int main() {
    vector<string> words = {"apple", "pear", "apple", "fig", "pear", "apple"};
 
    map<string, int> freq;
    for (const string& w : words) {
        ++freq[w];
    }
 
    for (const auto& [word, count] : freq) {
        cout << word << ": " << count << endl;
    }
 
    cout << "apple appears " << freq["apple"] << " times" << endl;
    cout << "distinct words: " << freq.size() << endl;
    return 0;
}

Output:

apple: 3
fig: 1
pear: 2
apple appears 3 times
distinct words: 3

This loop prints the words in alphabetical order, because map keeps its keys sorted. The line const auto& [word, count] is a C++17 form that names the two parts of each map entry, the key and the value, in one step. The method size gives the number of distinct keys, which is the number of different words.

The C++ unordered_map is the hashed version, like Java's HashMap, and it prints in no fixed order. Choose map when you want the output sorted, and unordered_map when you only need the counts.

Two-sum: two values that add up to a target

The two-sum problem asks for two values in a list whose sum equals a target number. The answer is their positions, not the values. For example, in the list 2, 7, 11, 15 with target 9, the values at positions 0 and 1 add up to 9, because 2 plus 7 is 9. The lesson assumes the answer is a pair of different positions, and that the program may report any one correct pair.

The direct solution checks every pair with two nested loops. The first loop picks a value, and the second loop checks every value after it for the partner. It is correct, but it does about n times n divided by 2 checks, so it slows down quickly.

The faster solution uses one idea. For each value x, its partner is target - x. Walk the list once, and at each value ask two things. Have I already seen the partner? If yes, the two positions are the answer. If no, remember this value with its position, so a later value can find it.

The map holds the values seen so far. The key is the value and the stored number is its position. Here is the walk for the list 2, 7, 11, 15 with target 9:

• Step 0: the value is 2 and its partner is 7. The map is empty, so 7 is not found. Store 2 at position 0.
• Step 1: the value is 7 and its partner is 2. The map holds 2 at position 0, so the partner is found. The answer is positions 0 and 1.

The walk stops at step 1 and never looks at 11 or 15. The order of steps matters. The program looks for the partner first, then stores the current value. The reason is explained in the mistakes section.

Worked example 2: finding the two positions

The Java version uses a containsKey check, then get to read the position. The C++ version uses find, which returns an iterator, and the iterator's second field holds the position.

import java.util.HashMap;
import java.util.Map;
 
public class Main {
    // Returns the indices of the two numbers that add up to target, or null.
    static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();  // value -> index
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (seen.containsKey(need)) {
                return new int[] {seen.get(need), i};
            }
            seen.put(nums[i], i);
        }
        return null;
    }
 
    static void show(int[] nums, int target) {
        int[] r = twoSum(nums, target);
        if (r == null) {
            System.out.println("target " + target + ": no pair");
        } else {
            System.out.println("target " + target + ": " + r[0] + " " + r[1]);
        }
    }
 
    public static void main(String[] args) {
        show(new int[] {2, 7, 11, 15}, 9);
        show(new int[] {3, 2, 4}, 6);
        show(new int[] {3, 3}, 6);
        show(new int[] {1, 2, 3}, 100);
    }
}

Output:

target 9: 0 1
target 6: 1 2
target 6: 0 1
target 100: no pair

The second line shows why the map stores positions and not just a yes or no. The list 3, 2, 4 with target 6 has its answer at positions 1 and 2, because 2 plus 4 is 6. When the walk reaches 4 at position 2, the partner 2 is in the map with position 1, and the method returns both positions.

The third line uses the same value twice, 3 and 3. At position 0 the map is empty, so 3 is stored. At position 1 the partner 3 is found at position 0. The answer is 0 and 1. The one-pass order makes this work without a special case. The walk never pairs a value with itself, because each value is looked up before it is stored.

The fourth line has no pair. The method returns null, and show prints "no pair". Returning a null for "no answer" is a choice this program made. The caller must check for it, as show does.

The C++ version returns a vector of two positions, and uses {-1, -1} for "no pair". Both positions are valid list indexes, so -1 cannot be one of them, which makes it a safe marker.

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
 
// Returns the indices of the two numbers that add up to target, or {-1, -1}.
vector<int> two_sum(const vector<int>& nums, int target) {
    unordered_map<int, int> seen;  // value -> index where it was seen
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        int need = target - nums[i];
        auto it = seen.find(need);
        if (it != seen.end()) {
            return {it->second, i};
        }
        seen[nums[i]] = i;
    }
    return {-1, -1};
}
 
int main() {
    vector<int> a = {2, 7, 11, 15};
    auto r1 = two_sum(a, 9);
    cout << "target 9: " << r1[0] << " " << r1[1] << endl;
 
    vector<int> b = {3, 2, 4};
    auto r2 = two_sum(b, 6);
    cout << "target 6: " << r2[0] << " " << r2[1] << endl;
 
    vector<int> c = {3, 3};
    auto r3 = two_sum(c, 6);
    cout << "target 6 with two 3s: " << r3[0] << " " << r3[1] << endl;
 
    vector<int> d = {1, 2, 3};
    auto r4 = two_sum(d, 100);
    cout << "target 100: " << r4[0] << " " << r4[1] << endl;
    return 0;
}

Output:

target 9: 0 1
target 6: 1 2
target 6 with two 3s: 0 1
target 100: -1 -1

The C++ function find returns the end position when the key is missing, so the check it != seen.end() tells the two cases apart. Using seen[need] for the same check would not work, and the mistakes section shows why.

Counting pairs with a frequency map

The third example combines both ideas. The question is how many pairs of positions i and j, with i less than j, have values that add up to the target. The list may have repeated values, so the answer can be more than one.

The one-pass idea still works. The map now stores how many times each value has been seen, which is a frequency map. For each value x, the number of earlier values equal to target - x is the number of pairs that end at x. Add that count to the total, then add x to the map. Because the map is updated after the lookup, each pair is counted once, from the position of its later value.

Worked example 3: counting pairs

Take the list 1, 5, 3, 3, 7, 5, 1. For target 6, the pairs are: 1 with 5 at positions 0 and 1, 1 with 5 at positions 0 and 5, 5 with 1 at positions 1 and 6, 5 with 1 at positions 5 and 6, and 3 with 3 at positions 2 and 3. That is five pairs. The Java program below finds five.

import java.util.HashMap;
import java.util.Map;
 
public class Main {
    // Counts pairs i < j with nums[i] + nums[j] == target, in one pass.
    static long countPairs(int[] nums, int target) {
        Map<Integer, Long> seen = new HashMap<>();  // value -> times seen so far
        long pairs = 0;
        for (int x : nums) {
            int need = target - x;
            pairs += seen.getOrDefault(need, 0L);
            seen.merge(x, 1L, Long::sum);
        }
        return pairs;
    }
 
    public static void main(String[] args) {
        int[] nums = {1, 5, 3, 3, 7, 5, 1};
        System.out.println("pairs summing to 6: " + countPairs(nums, 6));
        System.out.println("pairs summing to 10: " + countPairs(nums, 10));
        System.out.println("pairs summing to 100: " + countPairs(nums, 100));
    }
}

Output:

pairs summing to 6: 5
pairs summing to 10: 3
pairs summing to 100: 0

The same program in C++ looks like this:

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
 
// Counts pairs i < j with nums[i] + nums[j] == target, in one pass.
long long count_pairs(const vector<int>& nums, int target) {
    unordered_map<int, long long> seen;  // value -> how many times seen so far
    long long pairs = 0;
    for (int x : nums) {
        int need = target - x;
        auto it = seen.find(need);
        if (it != seen.end()) {
            pairs += it->second;
        }
        ++seen[x];
    }
    return pairs;
}
 
int main() {
    vector<int> nums = {1, 5, 3, 3, 7, 5, 1};
    cout << "pairs summing to 6: " << count_pairs(nums, 6) << endl;
    cout << "pairs summing to 10: " << count_pairs(nums, 10) << endl;
    cout << "pairs summing to 100: " << count_pairs(nums, 100) << endl;
    return 0;
}

Output:

pairs summing to 6: 5
pairs summing to 10: 3
pairs summing to 100: 0

Check the target 10 case by hand. The values 3 and 7 add to 10, and there are two 3s and one 7, so they make two pairs. The two 5s add to 10 as well, which makes one more pair. Three pairs in total, which matches the output.

The line pairs += seen.getOrDefault(need, 0L) in Java does the same job as the find check in C++. The 0L is a long zero, which matches the map's value type. Without it the call would not compile with a Long map.

Notice the program's cost. It reads the list once, and each value costs one lookup and one update. The map may hold as many entries as there are distinct values, so the extra memory grows with the number of different values, not with the number of pairs.

Common mistakes and the messages you will see

Mistake 1: storing the value before looking for its partner

If the program stores the current value first, a value can match itself. The list with one element 4 and target 8 has no pair, but the wrong order reports one.

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
 
// Wrong order: stores the value before looking for its partner.
vector<int> two_sum_store_first(const vector<int>& nums, int target) {
    unordered_map<int, int> seen;
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        seen[nums[i]] = i;
        auto it = seen.find(target - nums[i]);
        if (it != seen.end()) {
            return {it->second, i};
        }
    }
    return {-1, -1};
}
 
int main() {
    vector<int> one = {4};
    auto r = two_sum_store_first(one, 8);
    cout << "one 4, target 8: " << r[0] << " " << r[1] << endl;
    return 0;
}

Output:

one 4, target 8: 0 0

The program reports the position 0 twice. The value 4 was stored at position 0, and then the partner 4 was looked up and found at that same position. The fix is the order used in the lesson: look up the partner first, then store the value.

Mistake 2: using the bracket operator as a check in C++

In C++, seen[need] does more than read. If the key is missing, it creates the key with the value 0. A check written with [] therefore changes the map, and later checks see the new key. The program below tests with [] and then with count. The result is wrong.

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
 
int main() {
    // Wrong version: the check uses [] instead of find().
    vector<int> nums = {5, 3};
    int target = 8;
    unordered_map<int, int> seen;
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        int need = target - nums[i];
        if (seen[need] != 0 || seen.count(need)) {
            cout << "found partner for index " << i << endl;
        }
        seen[nums[i]] = i;
    }
    cout << "seen size " << seen.size() << endl;
    cout << "seen[3] reads index " << seen[3] << endl;
    return 0;
}

Output:

found partner for index 0
found partner for index 1
seen size 2
seen[3] reads index 1

At index 0, the value 5 needs a partner 3. The map does not hold 3, so seen[3] creates it with the value 0. The count that follows then finds the new key and reports a partner, even though no partner was stored. The message at index 0 is false. The fix is to use find and compare with end(), or to use count alone, and never use [] for a check.

Mistake 3: reading a missing key in Java

In Java, get returns null for a missing key. Assigning the result to an int makes Java try to turn the null into a plain number, and the program stops.

import java.util.HashMap;
import java.util.Map;
 
public class Main {
    public static void main(String[] args) {
        Map<String, Integer> freq = new HashMap<>();
        freq.put("apple", 3);
        int count = freq.get("kiwi");
        System.out.println(count);
    }
}

Output:

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null
	at Main.main(Main.java:8)

The message names the line, Main.java:8. The fix is getOrDefault(key, 0) when a missing key is a normal answer, or a check for null before you read the value.

Mistake 4: relying on the order of a Java HashMap

A HashMap does not keep its keys in any order you can predict from the input. The order depends on the hash codes of the keys. Looping over entrySet() prints the keys in that hidden order. The program below counts the same six words and prints the map directly.

import java.util.HashMap;
import java.util.Map;
 
public class Main {
    public static void main(String[] args) {
        Map<String, Integer> freq = new HashMap<>();
        for (String w : new String[] {"apple", "pear", "apple", "fig", "pear", "apple"}) {
            freq.merge(w, 1, Integer::sum);
        }
        for (Map.Entry<String, Integer> e : freq.entrySet()) {
            System.out.println(e.getKey() + " " + e.getValue());
        }
    }
}

Output on the JDK used for this lesson:

apple 3
pear 2
fig 1

The order here is not alphabetical. It happens to match the order of first appearance, apple, pear, fig, but that comes from the hash codes of the keys, not from the input. The output may differ on another Java version, so a program should not depend on it. When you need sorted output, use TreeMap, the Java version of a sorted map. The ordered sets and range lookups lesson in this module introduces that container.

Practice

Try each exercise before you open its answer. Each answer lists the expected output.

Exercise 1. A Java program counts the letters of the word "banana" with a HashMap<Character, Integer> and merge. Print how many times the letter a appears.

Show the answer

The output is 3. The code is:

Map<Character, Integer> counts = new HashMap<>();
for (char c : "banana".toCharArray()) {
    counts.merge(c, 1, Integer::sum);
}
System.out.println(counts.get('a'));

The word has three letters a, at positions 1, 3 and 5.

Exercise 2. Use the C++ two_sum idea from this lesson on the list {1, 4, 6, 9} with target 10. Which two positions are returned?

Show the answer

The positions are 1 and 2, so the output is 1 2. The walk stores 1 at position 0, then 4 at position 1. At position 2 the value is 6, and its partner 4 is in the map at position 1. Because 4 plus 6 is 10, the answer is positions 1 and 2.

Exercise 3. Use the C++ count_pairs function from this lesson on the list {5, 5, 5} with target 10. How many pairs are there?

Show the answer

The output is 3. Every pair of the three 5s adds up to 10. The three pairs are positions (0, 1), (0, 2) and (1, 2). The walk counts 0 pairs at the first 5, 1 pair at the second, and 2 pairs at the third, which is 3 in total.

Exercise 4. Run the Java twoSum from this lesson on the list {1, 2} with target 10. Print "no pair" when the method returns null.

Show the answer

The output is no pair. No two values in the list add up to 10, so the method reaches the end of the loop and returns null. The caller checks for null before it reads the positions.

Exercise 5. In the C++ list {3, 1, 3, 2, 3, 1}, find the value that appears most often, and print it with its count. Use a map to count the values.

Show the answer

The output is 3 appears 3 times. The count map is 1 with 2, 2 with 1, and 3 with 3. The program walks the map and keeps the value with the highest count. Code:

vector<int> nums = {3, 1, 3, 2, 3, 1};
map<int, int> freq;
for (int x : nums) {
    ++freq[x];
}
int best = nums[0];
for (const auto& [value, count] : freq) {
    if (count > freq[best]) {
        best = value;
    }
}
cout << best << " appears " << freq[best] << " times" << endl;

Summary

• A frequency map counts how often each value appears. It reads the input once and costs one lookup and one update per value.
• The two-sum walk looks up the partner first, then stores the current value. This order stops a value from pairing with itself.
• The stored position lets the map return the answer, not just a yes or no.
• In C++, find checks for a key without changing the map, while [] creates a missing key. Use find or count for checks.
• In Java, get returns null for a missing key, so use getOrDefault for counts or check for null first.
• A HashMap or unordered_map gives no order you can rely on. Use a sorted map when the output must be in order.