HashMap Patterns — Seen-Before & Frequency Counting

The cheapest optimisation in interviews: trade O(n) memory for O(1) lookups. Two shapes cover almost everything.

Shape 1: "Have I seen this before?" (Set / Map)

// Two Sum — THE interview classic, O(n)
function twoSum(nums, target) {
  const seen = new Map();                    // value → index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
}

The reframe that unlocks it: instead of "find two numbers that sum to target" (pairs → O(n²)), ask per element "have I already seen my complement?" (single pass → O(n)). Learning to reframe searches as lookups is the whole skill.

Shape 2: Frequency counter

function frequency(items) {
  const freq = new Map();
  for (const x of items) freq.set(x, (freq.get(x) ?? 0) + 1);
  return freq;
}

// Anagram check = same frequency profile
// First unique char = first with count 1
// Majority element = count > n/2

Spot it when…

• "Find a pair/complement" → seen-before Map
• "Count / most common / duplicates / anagram" → frequency counter
• Your brute force re-searches the same data repeatedly → cache it in a Map

Practice now

• Two Sum
• Valid Anagram
• First Non-Repeating Character
• Majority Element

Interview line: "I'll trade O(n) space for O(1) lookups" — announcing the trade-off is what earns the points. Deep dive: HashMaps blog post.