Frequency Counting & Two-Sum

With the "why" in hand, here are the two hash-map patterns you'll reach for most. Both share one move: remember what you've already seen so you never have to look back through the data.

Pattern one: counting occurrences

How many times does each item appear? A dictionary from item to count answers it in a single pass. Each item you meet, bump its count by one; use .get(key, 0) so the first sighting starts from zero instead of raising a KeyError.

def char_counts(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    return counts

print(char_counts("mississippi"))

{'m': 1, 'i': 4, 's': 4, 'p': 2}

What just happened: one walk through the string. counts.get(ch, 0) reads the running total (or 0 if this character is new), adds one, and stores it back. By the end every character maps to how often it appeared - i and s four times each. This is O(n): one lookup-and-update per character, each O(1) on average.

💡 Key point. The standard library has this exact pattern prepackaged as collections.Counter - so in real code you'd write Counter("mississippi"). Writing the loop by hand once is worth it to see there's no magic: it's just a dict and += 1.

Pattern two: two-sum in a single pass

The classic interview problem: given a list of numbers and a target, return the indices of the two numbers that add up to the target. The brute force checks every pair - O(n²). The two-pointer version gets it to O(n) but requires sorting first (and sorting scrambles the original indices). The hash map does it in one pass with no sorting at all.

The insight: as you walk the list, for each number x you know exactly what its partner must be - target - x, call it the complement. So instead of searching for the partner, ask a hash map "have I already seen target - x?" If yes, you've found the pair. If no, remember x (and its index) and move on.

def two_sum(nums, target):
    seen = {}                       # value -> index where we saw it
    for i, x in enumerate(nums):
        need = target - x           # the complement that would complete the pair
        if need in seen:
            return (seen[need], i)
        seen[x] = i
    return None

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))
print(two_sum([1, 2, 3], 100))

(0, 1)
(1, 2)
None

What just happened: for [2, 7, 11, 15] with target 9: see 2, its complement 7 isn't in seen yet, so remember 2. See 7, its complement 2 is in seen - return (0, 1). For [3, 2, 4] target 6, the pair is 2 + 4, found at indices (1, 2). Target 100 has no pair, so None. Each number is looked at once, and each "have I seen the complement?" check is an O(1) hash lookup - the whole thing is O(n).

⚠️ Gotcha. Store each number in seen after checking for its complement, not before. Check first, then insert. If you insert x first and the target happens to be 2 * x, the number would match itself and report a bogus pair of one element counted twice.

The one-pass two-sum, in other languages

The pattern travels cleanly: a hash map from value to index, one loop, check-then-insert. Each language brings its own map type and its own way of saying "not found."

[[codegroup One-Pass Two-Sum]]

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return (seen[need], i)
        seen[x] = i
    return None

function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return null;
}

function twoSum(nums: number[], target: number): [number, number] | null {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need)!, i];
    seen.set(nums[i], i);
  }
  return null;
}

static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    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;
}

// returns {-1, -1} when no pair is found
std::pair<int, int> two_sum(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;
    for (int i = 0; i < (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};
}

func twoSum(nums []int, target int) (int, int, bool) {
    seen := make(map[int]int)
    for i, x := range nums {
        need := target - x
        if j, ok := seen[need]; ok {
            return j, i, true
        }
        seen[x] = i
    }
    return 0, 0, false
}

use std::collections::HashMap;

fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    let mut seen: HashMap<i32, usize> = HashMap::new();
    for (i, &x) in nums.iter().enumerate() {
        let need = target - x;
        if let Some(&j) = seen.get(&need) {
            return Some((j, i));
        }
        seen.insert(x, i);
    }
    None
}

[[/codegroup]]

Every version trades a little memory (the seen map) for a lot of speed (O(n²) down to O(n)). That trade - remember more so you can scan less - is the beating heart of nearly every hash-map speedup.

[
  {
    "q": "In the one-pass two-sum, what is the \"complement\" the code looks up in the hash map?",
    "choices": ["The next number in the list", "target - x, the value that would complete the pair with the current number", "The largest number seen so far", "The index of x"],
    "answer": 1,
    "explain": "For a current number x, the only partner that reaches the target is target - x. Checking whether that complement was already seen finds the pair in one pass."
  },
  {
    "q": "Why must you check for the complement BEFORE inserting the current number into the map?",
    "choices": ["To save memory", "So a number isn't matched with itself when the target equals twice that number", "Because insertion is slower than lookup", "It doesn't matter which order you use"],
    "answer": 1,
    "explain": "If you insert x first and target == 2*x, the lookup would find x itself and report a fake pair. Check-then-insert prevents an element from pairing with itself."
  },
  {
    "q": "What does the hash-map two-sum gain over the two-pointer version?",
    "choices": ["It uses less memory", "It works on unsorted input without sorting, preserving the original indices", "It is O(log n)", "It never needs a loop"],
    "answer": 1,
    "explain": "The two-pointer approach needs sorted data (which scrambles indices). The hash map runs in one O(n) pass on unsorted input and returns the original positions."
  }
]