Frequency Counting (Hashing)

Frequency counting means walking through the input once and recording how many times each value appears, usually in a hash map or a fixed-size array. After that, many questions become simple lookups on the counts instead of nested loops. Interviewers like it because it tests whether you can trade a little memory for a big speedup, turning O(n^2) brute force into O(n).

When to use it

  • The question asks how many times something appears, or whether something appears more than once.
  • You need to compare two collections ignoring order (anagrams, permutations, same letters).
  • The question asks for the most common, least common, or top k items.
  • A brute-force solution would compare every pair or rescan the array for each element.
  • The values come from a small known set, like lowercase letters or digits, so a fixed-size count array works.

See it work

  1. Problem: are "listen" and "silent" anagrams? Two strings are anagrams if every letter appears the same number of times in both. We will count the letters of the first word, then cancel them out with the second. Start with an empty count map. [l, i, s, t, e, n]
  2. Pass 1: walk through "listen" and add 1 to each letter's count. Every letter is different, so each ends up with a count of 1: {l:1, i:1, s:1, t:1, e:1, n:1}. [l, i, s, t, e, n]
  3. Pass 2: walk through "silent". The first letter is 's'. Its count is 1, so subtract 1 and it becomes 0. A letter that is missing or already at 0 would mean the strings differ, so we could stop and return false. [s, i, l, e, n, t]
  4. Keep going: 'i' goes to 0, 'l' goes to 0, 'e' goes to 0, 'n' goes to 0. None of them ever needed a count below 0. [s, i, l, e, n, t]
  5. The last letter 't' goes from 1 to 0. All counts are 0 and both strings had length 6, so every letter matched. Answer: true. Total work was two passes, which is O(n). [s, i, l, e, n, t]

Code template

Python

from collections import defaultdict

def count_items(items):
    counts = defaultdict(int)   # value -> how many times seen
    for x in items:             # one pass to build the counts
        counts[x] += 1
    return counts

def has_duplicate(items):
    counts = count_items(items)
    # answer from the counts, not from rescanning the input
    for value, c in counts.items():
        if c > 1:
            return True
    return False

C

#include <stdbool.h>

// Fixed-size count array: works when values are small, e.g. 'a'..'z'.
bool has_duplicate_letter(const char *s) {
    int counts[26] = {0};          // letter -> how many times seen
    for (int i = 0; s[i] != '\0'; i++) {
        int idx = s[i] - 'a';
        counts[idx]++;             // one pass to build the counts
    }
    // answer from the counts, not from rescanning the input
    for (int k = 0; k < 26; k++) {
        if (counts[k] > 1) return true;
    }
    return false;
}

Java

import java.util.*;

class FrequencyCount {
    static Map<Integer, Integer> countItems(int[] items) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int x : items) {            // one pass to build the counts
            counts.put(x, counts.getOrDefault(x, 0) + 1);
        }
        return counts;
    }

    static boolean hasDuplicate(int[] items) {
        Map<Integer, Integer> counts = countItems(items);
        // answer from the counts, not from rescanning the input
        for (int c : counts.values()) {
            if (c > 1) return true;
        }
        return false;
    }
}

Complexity: Time is O(n) for one pass over n items, with O(1) average cost per hash map update. Space is O(k) where k is the number of distinct values, or O(1) if the values come from a fixed small set like 26 letters.

Programs that use it

Interview problems that use it

  • Valid Anagram: Count letters of the first string, subtract using the second, and check that every count ends at zero.
  • Contains Duplicate: Record each value as you see it; if a value is already in the map or set, a duplicate exists.
  • First Unique Character in a String: Count every character in pass one, then find the first character in pass two whose count is exactly 1.
  • Top K Frequent Elements: Build a count map, then pick the k values with the largest counts using a heap or bucket sort by frequency.
  • Group Anagrams: Use each word's letter-count signature (or sorted letters) as a map key so anagrams land in the same group.
  • Ransom Note: Count the letters available in the magazine, then spend one count per letter needed by the note and fail if any run out.

Common mistakes

  • Forgetting the default value: reading counts[x] for a missing key crashes or gives garbage. Use getOrDefault, defaultdict, or Counter, or initialize a count array to zeros.
  • Checking only that no count goes negative when comparing two collections. If the lengths differ, leftover positive counts can slip through, so compare lengths first or check that all counts end at zero.
  • Using a hash map when a plain array would do, or the reverse: for 26 lowercase letters an int[26] is faster and simpler, but arrays break when the input can contain uppercase letters, Unicode, or large numbers.

Frequently asked questions

When should I use a hash map versus a count array?

Use a count array when the possible values are a small, known range, such as 26 lowercase letters or digits 0-9. Use a hash map when values are arbitrary, such as large integers, negative numbers, or strings.

Is frequency counting always O(n) time?

Building the counts is O(n) on average since each hash map update is O(1) on average. Follow-up steps can cost more, for example sorting by frequency for top k adds O(d log d) for d distinct values, unless you use bucket sort.

How is frequency counting different from the two-pointer or sliding window pattern?

Frequency counting looks at the whole input and ignores order, so it answers 'how many of each?'. Sliding window cares about a contiguous range and often uses a count map inside the window, so the two patterns are frequently combined.

← All interview patterns

Try AI Flowchart free →