Frequency Counting and Complement Lookup

Beginner: frequency maps are labeled counters

Consider the word banana. You could keep six unrelated marks on paper, but a frequency map gives every distinct character a labeled counter:

b → 1
a → 3
n → 2

The key identifies the thing being counted; the value is its count. Build the map by reading one item at a time:

function countCharacters(text: string): Map<string, number> {
  const counts = new Map<string, number>()
  for (const character of text) {
    counts.set(character, (counts.get(character) ?? 0) + 1)
  }
  return counts
}

The invariant is: after processing the first i characters, each stored value equals that character’s frequency in the processed prefix.

Worked example: consumable inventory

Suppose a magazine provides aabcc, and a note needs cab. First count the available letters, then consume one count for every requested letter:

available starts as {a:2, b:1, c:2}
need c → 2 available → write c:1
need a → 2 available → write a:1
need b → 1 available → write b:0
all needs satisfied → true

If a requested count is missing or zero, return false. The meaning of the map is now “inventory remaining,” not merely “total frequency.”

function canConstruct(note: string, magazine: string): boolean {
  const available = countCharacters(magazine)
  for (const character of note) {
    const remaining = available.get(character) ?? 0
    if (remaining === 0) return false
    available.set(character, remaining - 1)
  }
  return true
}

Intermediate: complement lookup

When a pair must satisfy a target, ask what partner the current value needs. Look for that complement among previously processed values, then store the current value. Derive the lookup from the equation rather than memorizing a template:

current + partner = target
partner = target - current

for (let index = 0; index < nums.length; index += 1) {
  const needed = target - nums[index]
  if (seenAt.has(needed)) return [seenAt.get(needed)!, index]
  seenAt.set(nums[index], index)
}

Check before inserting when the same array element may not be used twice.

Worked trace: [3, 2, 4], target 6

i  current  needed  map before check  action
0  3        3       {}                store 3 → 0
1  2        4       {3 → 0}           store 2 → 1
2  4        2       {3 → 0, 2 → 1}    return [1, 2]

For [3, 3] and target 6, the first 3 is stored and the second 3 finds it. This uses two different indices while still supporting equal values.

One pass versus two passes

A two-pass solution can store every value first and look up complements second. It is still expected O(n), but it must explicitly reject a lookup that returns the current index. The one-pass version encodes “only earlier positions are candidates,” supports early return, and usually has the cleaner correctness argument.

Advanced: generalize the algebra

Complements appear whenever a required relationship can be rearranged around the current value:

• a - b = k suggests looking for a - k or b + k.
• A product target suggests target / current, after handling zero and divisibility.
• a XOR b = target suggests target XOR current because XOR reverses itself.

The syntax changes less than the reasoning. Ask which earlier state could pair with the current state, what key represents it, and whether you need existence, a count, or an index.

Common failure modes

• Forgetting to decrement a frequency used as consumable inventory.
• Returning values when the problem requests indices.
• Using truthiness to test an index that may be zero.
• Inserting before checking and allowing one element to match itself.
• Overwriting the earliest position when a later problem needs it preserved.

Recognition checklist

1. What repeated question would a brute-force solution ask?
2. Can its answer be stored under a stable key?
3. Do I need existence, a count, or an index?
4. What exactly does the structure contain after iteration i?
5. Does check-before-insert or insert-before-check preserve the rule?