Remembering What You Have Seen

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, Boyer–Moore voting, cancels each non-majority value against a majority value. Learn that optimization after you can explain why the count solution is correct.

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.