Counting and frequency tables

coreCommon atAmazonMetaGoogleBloombergRead firstHash mapsArraysPractise in the Sandbox →

A frequency table maps each distinct value to how many times it occurs. Build it in one O(n) pass, then every “how many X?” is an O(1) lookup. Use a hash map for open-ended values and a plain array when the values are small integers or letters.

The idea in plain words

You’re handed a bag of Scrabble tiles and asked “can I spell GAMER?” You wouldn’t search the bag once per letter. You’d tip it out, sort the tiles into little piles by letter, and count each pile. Then every question about the bag is a glance at one pile.

That pile-per-value table is the whole trick. Two passes beat nested loops:

• Pass 1, tally. For each item, count[item] += 1. No searching.
• Pass 2, ask. “Is there enough?”, “which occurs once?”, “which occurs most?” are now lookups.

Two collections have the same contents ignoring order (they’re equal as multisets) exactly when their frequency tables are equal. That single fact replaces sorting in a surprising number of problems.

See it

Type a set of letters you have and a word to build. Watch the tally phase fill the counts, then the spend phase drain them. The first count that goes below zero proves the answer is “no”, and you can stop right there.

Tally, then spend

step through

letters you have (a-z)word to build (a-z)

m

a

g

a

z

i

n

e

have

g

a

m

e

r

need

0

a

0

e

0

g

0

i

0

m

0

n

0

r

0

z

phasetally

answer…

just updatedcount went negativecount is 0

Goal: can "gamer" be spelled using the letters of "magazine", each letter used at most once? Start with every count at 0.

↺◀▶ Play▶1 / 14

When to reach for it

The problem says…	Why counting fits
“how many times does each… appear”, “histogram”	That’s literally a frequency table.
“same letters / same items in any order”	Equal multisets ⇔ equal count tables, no sorting needed.
“first item that appears once”, “any duplicate?”	Count in pass 1, scan in original order in pass 2.
“is there enough supply for the demand?”	Count the supply, subtract the demand, watch for negatives.
“most frequent”, “top k by frequency”	Count first, then pick (a max scan, a heap, or buckets by count).
values are bounded (letters, digits, ages, bytes)	An array of size k is a faster, smaller table than a map.

How it works

1. Choose the table: an array int[k] if values map to 0..k-1 cheaply (ch - 'a'), otherwise a hash map.
2. Tally: one pass, count[v] += 1.
3. Query: look up, compare, or decrement. For “enough of everything?”, decrement and fail fast on a negative.

With a fixed alphabet the table is just 26 integers:

Python

can_construct.py

def can_construct(word: str, letters: str) -> bool:
    """Can `word` be spelled from `letters`, each letter used at most once? Lowercase a-z only."""
    counts = [0] * 26  # 1. fixed alphabet: an array beats a hash map
    for ch in letters:
        counts[ord(ch) - ord("a")] += 1  # 2. tally the supply
    for ch in word:
        i = ord(ch) - ord("a")
        counts[i] -= 1  # 3. spend; going negative means we ran out
        if counts[i] < 0:
            return False
    return True


if __name__ == "__main__":
    assert can_construct("gamer", "magazine") is False  # no 'r'
    assert can_construct("gaze", "magazine")
    assert can_construct("aa", "ab") is False
    assert can_construct("", "")
    print("ok")

TypeScript

can_construct.ts

import assert from "node:assert/strict";

/** Can `word` be spelled from `letters`, each letter used at most once? Lowercase a-z only. */
export function canConstruct(word: string, letters: string): boolean {
  const counts = new Array<number>(26).fill(0); // 1. fixed alphabet: an array beats a Map
  const A = "a".charCodeAt(0);
  for (let i = 0; i < letters.length; i++) counts[letters.charCodeAt(i) - A]++; // 2. tally the supply
  for (let i = 0; i < word.length; i++) {
    const c = word.charCodeAt(i) - A;
    if (--counts[c] < 0) return false; // 3. spend; going negative means we ran out
  }
  return true;
}

assert.equal(canConstruct("gamer", "magazine"), false); // no 'r'
assert.equal(canConstruct("gaze", "magazine"), true);
assert.equal(canConstruct("aa", "ab"), false);
assert.equal(canConstruct("", ""), true);
console.log("ok");

C#

can_construct.cs

// Can `word` be spelled from `letters`, each letter used at most once? Lowercase a-z only.
static bool CanConstruct(string word, string letters)
{
    var counts = new int[26];            // 1. fixed alphabet: an array beats a Dictionary
    foreach (char ch in letters)
        counts[ch - 'a']++;              // 2. tally the supply (char arithmetic yields an int)
    foreach (char ch in word)
        if (--counts[ch - 'a'] < 0)      // 3. spend; going negative means we ran out
            return false;
    return true;
}

if (CanConstruct("gamer", "magazine")) throw new Exception("no 'r'");
if (!CanConstruct("gaze", "magazine")) throw new Exception("expected true");
if (CanConstruct("aa", "ab")) throw new Exception("expected false");
if (!CanConstruct("", "")) throw new Exception("expected true");
Console.WriteLine("ok");

For open-ended values, use the language’s counter. Note how each language handles ties: Python’s Counter.most_common and JS Map keep first-insertion order; C# Dictionary doesn’t promise any order, so you break ties against the input.

Python

first_unique / most_common.py

from collections import Counter


def first_unique(items: list[str]) -> int:
    """Index of the first item that occurs exactly once, or -1."""
    counts = Counter(items)  # 1. pass one: count everything
    for i, x in enumerate(items):  # 2. pass two: scan in the original order
        if counts[x] == 1:
            return i
    return -1


def most_common(items: list[str]) -> str | None:
    """Most frequent item; ties go to the one seen first."""
    if not items:
        return None
    counts = Counter(items)
    # 3. Counter.most_common keeps first-seen order among equal counts
    return counts.most_common(1)[0][0]


if __name__ == "__main__":
    assert first_unique(list("leetcode")) == 0
    assert first_unique(list("loveleetcode")) == 2
    assert first_unique(list("aabb")) == -1
    assert most_common(["b", "a", "b", "a", "c"]) == "b"
    assert most_common([]) is None
    print("ok")

TypeScript

first_unique / most_common.ts

import assert from "node:assert/strict";

function tally<T>(items: T[]): Map<T, number> {
  const counts = new Map<T, number>();
  for (const x of items) counts.set(x, (counts.get(x) ?? 0) + 1);
  return counts;
}

/** Index of the first item that occurs exactly once, or -1. */
export function firstUnique(items: string[]): number {
  const counts = tally(items); // 1. pass one: count everything
  return items.findIndex((x) => counts.get(x) === 1); // 2. pass two: scan in the original order
}

/** Most frequent item; ties go to the one seen first. */
export function mostCommon(items: string[]): string | undefined {
  let best: string | undefined;
  let bestCount = 0;
  // 3. Map iterates in insertion order, so a strict > keeps the first-seen winner on ties
  for (const [x, c] of tally(items)) if (c > bestCount) { best = x; bestCount = c; }
  return best;
}

assert.equal(firstUnique([..."leetcode"]), 0);
assert.equal(firstUnique([..."loveleetcode"]), 2);
assert.equal(firstUnique([..."aabb"]), -1);
assert.equal(mostCommon(["b", "a", "b", "a", "c"]), "b");
assert.equal(mostCommon([]), undefined);
console.log("ok");

C#

first_unique / most_common.cs

// Index of the first item that occurs exactly once, or -1.
static int FirstUnique(IList<string> items)
{
    var counts = new Dictionary<string, int>();
    foreach (var x in items) counts[x] = counts.GetValueOrDefault(x) + 1; // 1. pass one: count
    for (int i = 0; i < items.Count; i++)                                // 2. pass two: original order
        if (counts[items[i]] == 1) return i;
    return -1;
}

// Most frequent item; ties go to the one seen first.
static string? MostCommon(IList<string> items)
{
    var counts = new Dictionary<string, int>();
    foreach (var x in items) counts[x] = counts.GetValueOrDefault(x) + 1;
    string? best = null;
    int bestCount = 0;
    // 3. Dictionary order is unspecified, so walk the input to break ties by first appearance
    foreach (var x in items)
        if (counts[x] > bestCount) { best = x; bestCount = counts[x]; }
    return best;
}

static List<string> Chars(string s) => s.Select(c => c.ToString()).ToList();

if (FirstUnique(Chars("leetcode")) != 0) throw new Exception("expected 0");
if (FirstUnique(Chars("loveleetcode")) != 2) throw new Exception("expected 2");
if (FirstUnique(Chars("aabb")) != -1) throw new Exception("expected -1");
if (MostCommon(["b", "a", "b", "a", "c"]) != "b") throw new Exception("expected b");
if (MostCommon([]) is not null) throw new Exception("expected null");
Console.WriteLine("ok");

The counting idioms in each language

	Python	TypeScript	C#
increment	c[x] = c.get(x, 0) + 1 or Counter	m.set(x, (m.get(x) ?? 0) + 1)	d[x] = d.GetValueOrDefault(x) + 1
whole tally	Counter(items)	loop (no built-in)	items.GroupBy(x => x).ToDictionary(g => g.Key, g => g.Count()) or items.CountBy(x => x) (.NET 9+)
letter index	ord(ch) - ord('a')	s.charCodeAt(i) - 97	ch - 'a'
compare tables	Counter(a) == Counter(b)	compare sizes, then each entry	compare Count, then each entry
top k	Counter.most_common(k)	sort entries	OrderByDescending(kv => kv.Value).Take(k)

Counter arithmetic

Python’s Counter supports a - b (drops non-positive counts), a & b (min), a | b (max) and a + b. Counter(word) - Counter(letters) is empty exactly when letters covers word. Neat in Python; in an interview, be ready to say what it costs (O(size of both)).

What it costs

	Time	Space
build a table	O(n)	O(d) distinct values (map) or O(k) (array)
one lookup	O(1) average (map), O(1) (array)
compare two tables	O(d) or O(k)
most frequent	O(d) scan after counting
top k by frequency	O(d log k) with a heap, or O(n) with buckets indexed by count	O(d)

Versus sorting: comparing two lists by sorting is O(n log n); counting is O(n). The catch is the table size. A int[26] is free; an int[2^31] is not.

Compare two lists of n items: sort or count?

drag the sliders

n (items) = 1,024 (2¹⁰)k (possible values) = 32 (2⁵)

sort both, then compare

20,480

count with a hash map

2,048

count into array[k]

2,080

A fixed array is the fastest counter when k is small (26 letters, 256 bytes, ages 0-150): no hashing, contiguous memory. Slide k past n and the array costs more to allocate and scan than the data itself; a hash map only pays for values that actually occur.

Variations you’ll meet

• Bucket by count. After counting, put each value into buckets[count]. Counts are at most n, so walking buckets from high to low gives “top k most frequent” in O(n).
• Running counts inside a window. Add on the right, subtract on the left, track “how many keys meet the target” in a separate integer. See sliding window.
• Prefix counts. seen[prefix_sum] counts how many earlier prefixes had a given value, which counts subarrays. See prefix sums.
• Counting sort. When values are in 0..k-1, counts directly produce sorted output in O(n + k). See sorting.
• Majority vote (Boyer-Moore). If one value occurs more than n/2 times, you can find it with O(1) space: keep a candidate and a counter. A neat contrast to the O(d) table.
• Approximate counting. When distinct values don’t fit in memory: Count-Min Sketch (frequencies) or HyperLogLog (number of distinct values). Worth naming at scale.

Pitfalls

• Wrong alphabet assumption. ch - 'a' crashes or corrupts on uppercase, digits, spaces or non-ASCII. Ask what characters can appear, and use a map if unsure.
• Using len(map) as “distinct count” after decrementing. Keys with count 0 still sit in the map. Delete them when they hit zero.
• Assuming tie order. “Most frequent” with ties needs a rule. Python Counter and JS Map are insertion ordered; C# Dictionary is not.
• Python’s defaultdict / Counter reads. Counter returns 0 for missing keys without inserting; defaultdict inserts on read, so a lookup quietly grows the table.
• Comparing maps in TS. map1 === map2 compares references. Compare sizes, then entries.

In the interview

• Ask about the value domain: “lowercase letters only? Unicode? Can numbers be negative or huge?” The answer decides array vs map.
• Say the two-pass plan out loud: “Tally in one pass, then answer from the table. O(n) time, O(k) space for k distinct values.”
• If space is tight, mention the alternatives: sort in place (O(1) extra, O(n log n) time), or Boyer-Moore for a majority.
• Follow-ups to expect: “the input is a stream” (keep counts incrementally), “too many distinct values to fit” (shard by hash, or a sketch).

Check yourself

Check yourself

pick one

You check whether string b is a rearrangement of string a by counting a's letters, then decrementing for each letter of b. Besides 'no count goes negative', what else must you check?

ANothing elseBThat a and b have the same length (or that every count ends at exactly 0)CThat both strings are sorted

Check yourself

pick one

Values are 64-bit user ids, n = 1,000 of them. Which table?

AAn array indexed by idBA hash mapCEither, same cost

Practice on your own

Classic textbook exercises, not gym questions:

• Find the difference: t is s shuffled plus one extra letter; which letter?
• Find all the elements of an array of 1..n that appear twice, using O(1) extra space (hint: the array can be its own table).
• Sort characters of a string by decreasing frequency.
• Majority element with Boyer-Moore voting, then the “more than n/3” version.

Go deeper

• Python docs: collections.Counter, including most_common ordering and multiset operations.
• CLRS, §8.2 “Counting sort”: the counting idea as a sorting algorithm and its O(n + k) bound.
• Boyer and Moore, “MJRTY: A Fast Majority Vote Algorithm”, the original O(1)-space majority trick, explained by its author.
• Cormode and Muthukrishnan, “An improved data stream summary: the Count-Min sketch” (2005), for counting when exact tables don’t fit.

Related

Hash maps and setsThe table underneath most counters.

Sliding windowCounts that update as a range moves.

Prefix sumsCounting earlier prefixes to count subarrays.

HeapsTop k by frequency after counting.