Introduction to Knowing What to Track

The state an algorithm stores determines what it can answer efficiently. I often need a count of each value or a record of values already seen. These records can replace repeated searches through the input.

Count first, then use the counts

Frequency counting has two phases. I first scan the input and record how often each value appears. I then use that record to answer the actual question, such as finding a duplicate or comparing two inputs.

I find it useful for most or least frequent values, exact occurrence checks, comparisons between datasets, and duplicate detection. The common signal is that a value matters because of how many times it appears. The examples below use both a duplicate check and a permutation check.

Examples and storage choices

I used frequency counting to find whether an array contains a duplicate:

function hasDuplicate(nums) {
  const counts = {};

  // Counting phase
  for (let num of nums) {
    counts[num] = (counts[num] || 0) + 1;
  }

  // Utilization phase
  for (let num in counts) {
    if (counts[num] > 1) {
      return true; // Found a duplicate!
    }
  }
  return false;
}

I also used it to check whether two strings are permutations of each other:

function arePermutations(str1, str2) {
  if (str1.length !== str2.length) return false;

  const counts = {};

  // Count characters in first string
  for (let char of str1) {
    counts[char] = (counts[char] || 0) + 1;
  }

  // Decrement for second string
  for (let char of str2) {
    if (!counts[char]) return false;
    counts[char]--;
  }

  // All should be zero if they're permutations
  return Object.values(counts).every((count) => count === 0);
}

A hash map is the common choice. I use each element as a key and its frequency as the value:

const frequency = {};
for (let item of data) {
  frequency[item] = (frequency[item] || 0) + 1;
}

When the values are small integers, an array can use the value as an index:

const frequency = new Array(26).fill(0); // For lowercase letters
for (let char of str) {
  frequency[char.charCodeAt(0) - "a".charCodeAt(0)]++;
}

Complexity and checklist

The counting pass is O(n), followed by a scan of the distinct values. A hash map uses O(k) space for k distinct values, while a fixed array uses space tied to its chosen range. Identifying the required state before writing code keeps the rest of the solution direct.

First, identify the value that the algorithm must retrieve later. Then check whether a count, membership flag, or index can represent it. That question usually reveals the smallest useful state.