Hash Maps and Sets

// Template 1: a Set of everything already passed. Answers "have I seen this before?" in O(1) on average,
// so the inner "search the earlier elements" loop of the brute force disappears.
export function firstRepeat(items) {
  const seen = new Set();
  for (const x of items) {
    if (seen.has(x)) return x;   // second sighting: the first value to repeat
    seen.add(x);
  }
  return null;                   // every value was distinct
}

// Template 2: a frequency map. Count once, then answer "how many?" for any value in O(1).
export function countAll(items) {
  const count = new Map();
  for (const x of items) count.set(x, (count.get(x) ?? 0) + 1);
  return count;
}

// Counting as a budget: can `note` be written using each letter of `magazine` at most once?
export function canConstruct(note, magazine) {
  const count = countAll(magazine);
  for (const ch of note) {
    const left = count.get(ch) ?? 0;
    if (left === 0) return false;   // this letter has run out
    count.set(ch, left - 1);        // spend one copy
  }
  return true;
}

// Template 3: complement lookup. For each x, the partner it needs is target - x: look it up among the values
// already passed, THEN record x. Looking up first means x never pairs with itself.
export function countPairs(nums, target) {
  const seen = new Map();   // value → how many times it has appeared so far
  let pairs = 0;
  for (const x of nums) {
    pairs += seen.get(target - x) ?? 0;   // x pairs with every earlier copy of its complement
    seen.set(x, (seen.get(x) ?? 0) + 1);
  }
  return pairs;
}

// Template 4: group by a canonical key. Items that should end up together must map to the same key:
// a length, a sorted string, a count signature, an encoded coordinate…
export function groupBy(items, keyOf) {
  const groups = new Map();   // key → items with that key, in input order
  for (const item of items) {
    const key = keyOf(item);
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(item);
  }
  return [...groups.values()];
}