Frequency counting

When to use it

Use it when the answer depends on how many times each value appears, and where the values stand does not matter.

It belongs to the foundations group: Remember what you have seen, in a shape that makes the next question take one step.

Watch it work

A shop lists every sale of the day, one item to a line. Return the items that sold at least need times, so the shop can order more of them.

Input
sales = ["tea", "milk", "tea", "rice", "tea", "milk"]
need = 3

Output
["tea"]

The method

1. Start with an empty table of counts
2. Add 1 to the count of each item sold
3. Keep each item whose count is high enough
4. Return the items kept

The run, one moment at a time

1. Step 1. Nothing is counted yet, so the table of counts is empty.

   sales: tea milk tea rice tea milk
   item: empty
   count: empty
   answer: empty
   

2. Step 2. "tea" is not in the table yet. Start from 0 and add 1: its count is 1.

   sales: tea milk tea rice tea milk
   item: tea
   count: 1
   answer: empty
   

3. Step 2. "milk" is not in the table yet. Start from 0 and add 1: its count is 1.

   sales: tea milk tea rice tea milk
   item: tea milk
   count: 1 1
   answer: empty
   

4. Step 2. "tea" is in the table with 1. Add 1: its count is 2.

   sales: tea milk tea rice tea milk
   item: tea milk
   count: 2 1
   answer: empty
   

5. Step 2. "rice" is not in the table yet. Start from 0 and add 1: its count is 1.

   sales: tea milk tea rice tea milk
   item: tea milk rice
   count: 2 1 1
   answer: empty
   

6. Step 2. "tea" is in the table with 2. Add 1: its count is 3.

   sales: tea milk tea rice tea milk
   item: tea milk rice
   count: 3 1 1
   answer: empty
   

7. Step 2. "milk" is in the table with 1. Add 1: its count is 2.

   sales: tea milk tea rice tea milk
   item: tea milk rice
   count: 3 2 1
   answer: empty
   

8. Step 3. "tea" has a count of 3. That is at least 3, so keep it.

   sales: tea milk tea rice tea milk
   item: tea milk rice
   count: 3 2 1
   answer: tea
   

9. Step 3. "milk" has a count of 2. That is below 3, so leave it out.

   sales: tea milk tea rice tea milk
   item: tea milk rice
   count: 3 2 1
   answer: tea
   

10. Step 3. "rice" has a count of 1. That is below 3, so leave it out.

    sales: tea milk tea rice tea milk
    item: tea milk rice
    count: 3 2 1
    answer: tea
    

11. Step 4. 6 sales, each counted once. Sold 3 times or more: tea.

    sales: tea milk tea rice tea milk
    item: tea milk rice
    count: 3 2 1
    answer: tea
    

The code

The numbered comments are the steps of the method.

function solve(sales, need) {
  // 1. Start with an empty table of counts
  const counts = new Map();
  // 2. Add 1 to the count of each item sold
  for (const item of sales) {
    counts.set(item, (counts.get(item) || 0) + 1);
  }
  // 3. Keep each item whose count is high enough
  const often = [];
  for (const [item, count] of counts) {
    if (count >= need) often.push(item);
  }
  // 4. Return the items kept
  return often;
}

def solve(sales, need):
    # 1. Start with an empty table of counts
    counts = {}
    # 2. Add 1 to the count of each item sold
    for item in sales:
        counts[item] = counts.get(item, 0) + 1
    # 3. Keep each item whose count is high enough
    often = []
    for item, count in counts.items():
        if count >= need:
            often.append(item)
    # 4. Return the items kept
    return often

How to spot it

Asked: Which values appear most often, or at least k times?

How often is a question about counts. Count every value first, then choose from the counts.

Asked: Do two lists hold the same items, in any order?

When order does not matter, two lists hold the same items exactly when every value has the same count in both.

Given: Only lowercase letters, so at most 26 different values

The table of counts stays small however long the input is. A list of 26 numbers can be the whole table.

Looks like it, but is not

• You only need to know whether a value appears at all, or appears again. Use Hash set membership. Seen or not seen is yes or no. A set answers it without keeping a number.
• You need where a value was, or which other item belongs with it. Use Hash map lookup. A count cannot say where. Keep the position or the partner beside the key, not a number.
• The counts are needed for every stretch of k items in a row. Use Fixed-size sliding window. Counting each stretch from nothing repeats work. Move along instead: add the item that enters and take off the item that leaves.

Cost and mistakes

Time grows with the number of items, written O(n): one step to count each item, then one step for each different value. Extra space is one count for each different value.

Watch out

• A value met for the first time has no count yet. Start from 0 before you add 1. If you forget, JavaScript stores NaN and Python raises a KeyError.
• Finish counting before you compare counts. A count read during the first pass covers only the items met so far.

In the 150

3 problems of the 150 use it. Naming them gives their method away, so the list is folded.