Sets and Maps: Track Seen Values, Counts, and Partners

The repeated-search alarm

A brute-force array solution often scans earlier values again and again. If every new value asks a question about the processed prefix, store the answer as you go.

Three questions cover many early interview problems:

1. Have I seen this value? Store membership in a Set.
2. How many times have I seen it? Store value → count in a Map.
3. Which earlier value does this one need? Store value → useful information, often an index, and look up a derived partner.

Set pattern: have I seen it?

Contains Duplicate (LeetCode #217) gives an integer array and asks whether any value appears more than once. Comparing every pair is O(n²). Instead, maintain this invariant:

Before processing the current value, seen contains every earlier value.

function containsDuplicate(nums: number[]): boolean {
  const seen = new Set<number>()
  for (const value of nums) {
    if (seen.has(value)) return true
    seen.add(value)
  }
  return false
}

The Set does not make the problem “free.” It spends memory to avoid rescanning.

Map pattern: how many times?

Valid Anagram (LeetCode #242) gives two strings and asks whether one is a rearrangement of the other with exactly the same character counts. First reject unequal lengths. Then increment counts for the first string and consume them with the second:

function isAnagram(source: string, candidate: string): boolean {
  if (source.length !== candidate.length) return false

  const remaining = new Map<string, number>()
  for (const character of source) {
    remaining.set(character, (remaining.get(character) ?? 0) + 1)
  }

  for (const character of candidate) {
    const available = remaining.get(character) ?? 0
    if (available === 0) return false
    remaining.set(character, available - 1)
  }
  return true
}

The Map’s meaning is not merely “frequency.” During the second loop it means unused source characters remaining. Naming the meaning makes the zero check obvious.

Majority Element (LeetCode #169) asks for the value occurring more than ⌊n/2⌋ times. The same frequency Map gives an O(n)-time, O(n)-space first solution. An advanced O(1)-space method is called Boyer–Moore voting.

The idea is pairing and cancellation. If you remove one occurrence of the true majority and one occurrence of any different value, the majority still remains the majority of what is left. Because it originally occupies more than half the array, different values cannot cancel all of its occurrences.

Keep one candidate and a balance:

• When the balance is zero, the current value becomes the new candidate.
• Seeing the candidate adds one to the balance.
• Seeing a different value subtracts one, representing a canceled pair.

For [2, 2, 1, 1, 1, 2, 2]:

value  candidate  balance  explanation
2      2          1        choose 2
2      2          2        another 2
1      2          1        cancel one 2 with one 1
1      2          0        cancel the remaining pair
1      1          1        balance was zero, choose 1
2      1          0        cancel 1 with 2
2      2          1        choose 2; it survives

function majorityElement(nums: number[]): number {
  let candidate = nums[0]
  let balance = 0

  for (const value of nums) {
    if (balance === 0) candidate = value
    balance += value === candidate ? 1 : -1
  }

  return candidate
}

This code assumes the problem guarantees that a majority exists. Without that guarantee, make a second pass to count the candidate and verify it actually appears more than ⌊n/2⌋ times. Learn this optimization after the frequency-Map solution is clear: the space improvement is useful, but its proof is less obvious.

Map pattern: which partner is needed?

Two Sum (LeetCode #1) gives nums and target and asks for two distinct indices whose values add to the target. Derive the lookup from the required relationship:

earlier + current = target
earlier = target - current

Store each earlier value with its index. Check before inserting so the current element cannot pair with itself:

function twoSum(nums: number[], target: number): [number, number] | undefined {
  const seenAt = new Map<number, number>()

  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)
  }
}

Details that cause real bugs

Use map.has(key) when a stored value may be 0. if (map.get(key)) incorrectly treats index zero and count zero as absence. Decide whether duplicate keys should preserve the earliest index or replace it; the problem determines which information is useful.

Week 2 opens the data structure itself—hashes, buckets, collisions, canonical keys, and prefix-map combinations. For now, the recognition skill is enough: identify the repeated question, store its answer under a stable key, and state the invariant.

Common mistakes

• Using a Set when the answer needs a count or index.
• Inserting before checking in Two Sum and reusing one element.
• Testing a retrieved index by truthiness.
• Saying O(1) space when the structure may hold all n values.
• Writing Map syntax before deciding what each entry means.