Frequency Counting and Complement Lookup

Frequency Maps: Count Occurrences by Key

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
}

Complement Lookup: Find the Missing Partner

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 first records every value and its index. A second loop computes the needed complement and looks it up. This can work, but the Map already contains the current element, so the code must explicitly reject using the same index twice.

For [3, 2, 4] with target 6, the first pass might build:

3 → 0
2 → 1
4 → 2

During the second pass, index 0 contains 3 and needs another 3. The Map returns index 0—the same element—so that result is invalid. The loop has to continue. This extra case is easy to forget, especially when the target is twice one array value.

A one-pass solution avoids that ambiguity by giving the Map a stricter meaning:

Before checking index i, the Map contains only values from indices smaller than i.

That invariant makes self-matching impossible. It also allows an early return as soon as the later half of a pair is reached. Both approaches use expected O(n) time and O(n) space, but the one-pass approach usually has the simpler correctness explanation.

Extend Complement Lookup to Other Pair Relationships

Complements appear whenever a required relationship can be rearranged around the current value. “Complement” does not always mean subtraction from a sum; it means the missing earlier value that would complete the required relationship.

Difference relationships

Suppose the pair must satisfy:

later - earlier = 4

When the current, later value is 11, isolate the earlier value:

earlier = later - 4
earlier = 11 - 4
earlier = 7

Look for 7 among previously seen values. The direction matters: earlier - later = 4 would produce a different lookup. Write the equation with the roles named before moving symbols around.

Product relationships

If earlier × current = 20 and the current value is 4, the needed earlier value is 20 / 4 = 5. Division introduces conditions that addition does not:

• Current value zero cannot be used as a divisor.
• If the problem uses integers, a non-divisible result such as 20 / 3 is not a valid integer complement.
• A target of zero needs separate reasoning because any pair containing zero has product zero.

The algebra gives a candidate lookup, but the input rules determine whether that lookup is valid.

XOR relationships

XOR compares the bits of two integers. A result bit is 1 when the two input bits differ. Two identities make it reversible:

x XOR x = 0
x XOR 0 = x

Starting from earlier XOR current = target, XOR both sides with current:

earlier = target XOR current

For target 6 and current value 3, the needed value is 6 XOR 3 = 5:

5 = 101₂
3 = 011₂
    -----
6 = 110₂

So if 5 appeared earlier, it forms a valid XOR pair with the current 3.

The syntax changes less than the reasoning. Ask which earlier state could pair with the current state, what key represents it, and whether the Map should store 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?