Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Book a call

Coding · Arrays and hashing

Count tables

Lesson · 10 min read · Arrays and hashing · Counting with a table

Value to count. With a small alphabet the table is a fixed array; with any other keys it is a map. Both answer the same questions.

A count per value

A count table maps a value to the number of times we've seen it so far. We build it in one pass, and after that it'll tell us whether two collections hold the same things in a different order, which of the values turn up most often, or whether one of them has gone over a limit we were given.

If the keys come from a small fixed range (the 26 lowercase letters, say, or the ten digits), I'd use an array indexed by c − 'a' in place of a map. It's really a hash map whose hash function can't collide. It costs you 26 integers however long the input gets, and in any of the languages you're likely to be interviewing in, it'll run several times faster than a general map.

One table, up and down

You don't need two tables to compare two collections. Add 1 for each item of the first and take 1 off for each item of the second. If they hold the same items, repeats included, you'll find that all of the entries have come back to 0 by the end.

If we slide the same table along a longer text, with one letter coming in and one going out at a time, it'll find all of the places where an anagram of the word begins. You'll meet that again as a fixed window in the sliding-window chapter.

Are "aab" and "aba" anagrams?

  1. Step 1 / 7
    s
    a0a1b2
    t
    a0b1a2
    count[a]1

    s[0] = a: count[a] goes up to 1.

  2. Step 2 / 7
    s
    a0a1b2
    t
    a0b1a2
    count[a]2

    s[1] = a: count[a] goes up to 2.

  3. Step 3 / 7
    s
    a0a1b2
    t
    a0b1a2
    count[a]2count[b]1

    s[2] = b: count[b] goes up to 1.

  4. Step 4 / 7
    s
    a0a1b2
    t
    a0b1a2
    count[a]1count[b]1

    t[0] = a: count[a] goes down to 1.

  5. Step 5 / 7
    s
    a0a1b2
    t
    a0b1a2
    count[a]1count[b]0

    t[1] = b: count[b] goes down to 0.

  6. Step 6 / 7
    s
    a0a1b2
    t
    a0b1a2
    count[a]0count[b]0

    t[2] = a: count[a] goes down to 0.

  7. Step 7 / 7
    s
    a0a1b2
    t
    a0b1a2
    count[a]0count[b]0

    Every count is back to 0: the words are anagrams.

Count first, then rank

To find the k most frequent values, we build the table first and then sort its distinct values by count. The sort only has to deal with the d distinct values, and there are often far fewer of those than n. In the trace below we count the values, sort them with ties going to the smaller value, and take the first k.

Since a count can't be bigger than n, we can also use the counts to index an array. Put a value in bucket number count, then read the buckets from the top until you've collected k of them. That's O(n) with no comparison sort, and it's the follow-up you'll usually be asked for once you've given the sorted version.

TimeO(n + d log d), or O(n) with buckets
SpaceO(n) for the table

A heap of size k gets you O(n log k). That's the answer I'd give if the values were coming in as a stream that we couldn't store.

The 2 most frequent values in [4, 4, 4, 6, 6, 6, 5, 5].

  1. Step 1 / 11
    nums
    4041426364655657
    k2

    First job: count. One pass, a map from value to how often it has appeared.

  2. Step 2 / 11
    nums
    40i41426364655657
    counts{4:1}

    4 → 1.

  3. Step 3 / 11
    nums
    4041i426364655657
    counts{4:2}

    4 → 2.

  4. Step 4 / 11
    nums
    404142i6364655657
    counts{4:3}

    4 → 3.

  5. Step 5 / 11
    nums
    40414263i64655657
    counts{4:3, 6:1}

    6 → 1.

  6. Step 6 / 11
    nums
    4041426364i655657
    counts{4:3, 6:2}

    6 → 2.

  7. Step 7 / 11
    nums
    404142636465i5657
    counts{4:3, 6:3}

    6 → 3.

  8. Step 8 / 11
    nums
    40414263646556i57
    counts{4:3, 6:3, 5:1}

    5 → 1.

  9. Step 9 / 11
    nums
    4041426364655657i
    counts{4:3, 6:3, 5:2}

    5 → 2.

  10. Step 10 / 11
    by count
    406152
    counts4:3 6:3 5:2

    Second job: order the 3 distinct values by count, largest first, smaller value first on a tie: [4, 6, 5].

  11. Step 11 / 11
    by count
    406152
    k2

    Take the first 2: [4, 6].

Problems in this module