Maps & sets

const words = ["apple", "bob", "apple", "cy"];
const lengths = new Map(
  words.map((w) => [w, w.length]),
);
// Map(3) {"apple" => 5, "bob" => 3, "cy" => 2}
const last = new Map(words.map((w, i) => [w, i]));
// Map(3) {"apple" => 2, "bob" => 1, "cy" => 3}
const firstSeen = new Set(words);
// Set(3) {"apple", "bob", "cy"}
const byLen = Map.groupBy(words, (w) => w.length);
[...byLen.keys()]; // [5, 3, 2]
byLen.get(5); // ["apple", "apple"]

const names = ["ann", "bo"];
const loose = names.map((n, i) => [n, i]);
// (string | number)[][]: not pairs
const pairs = names.map((n, i) => [n, i] as const);
const ids = new Map(pairs); // Map<string, number>
ids.get("bo"); // 1
 
const any = new Map(); // Map<any, any>: nothing checked
any.set("a", 1);
const oops: string = any.get("a"); // compiles anyway

const stock = new Map([["apple", 3], ["pear", 0]]);
stock.get("apple"); // 3
stock.get("kiwi"); // undefined
stock.get("kiwi") ?? 0; // 0
stock.has("pear"); // true
 
stock.set("kiwi", 5).set("apple", 4); // chained
[...stock.keys()]; // ["apple", "pear", "kiwi"]
stock.delete("pear"); // true
stock.delete("plum"); // false: wasn't there
stock.size; // 2
 
const counts = new Map<string, number>();
for (const ch of "banana") {
  counts.set(ch, (counts.get(ch) ?? 0) + 1);
}
counts; // Map(3) {"b" => 1, "a" => 3, "n" => 2}

const groups = new Map<string, string[]>();
for (const w of ["eat", "tea", "tan"]) {
  const key = [...w].sort().join("");
  groups.getOrInsertComputed(key, () => []).push(w);
}
groups; // Map(2) {"aet" => ["eat", "tea"], "ant" => ["tan"]}

const groups = new Map<string, string[]>();
for (const w of ["eat", "tea", "tan"]) {
  const key = [...w].sort().join("");
  let list = groups.get(key);
  if (!list) groups.set(key, (list = []));
  list.push(w);
}
groups; // Map(2) {"aet" => ["eat", "tea"], "ant" => ["tan"]}

const score = new Map([["ann", 90], ["bo", 72], ["cy", 90]]);
const keys = score.keys(); // a live iterator
score.set("di", 85);
[...keys]; // ["ann", "bo", "cy", "di"]
[...keys]; // []: used up
 
const ranked = [...score].sort(
  (a, b) => b[1] - a[1] || a[0].localeCompare(b[0]),
);
// [["ann", 90], ["cy", 90], ["di", 85], ["bo", 72]]
 
let best = "";
let top = -Infinity;
for (const [name, s] of score) {
  if (s > top) [best, top] = [name, s];
}
best; // "ann": the first of the ties
 
score.values().filter((s) => s >= 85).toArray();
// [90, 90, 85]

const live = new Map([["a", 1], ["b", 2], ["c", 3]]);
const seen: string[] = [];
for (const [k] of live) {
  seen.push(k);
  if (k === "a") {
    live.delete("b"); // not reached yet: skipped
    live.set("d", 4); // added: visited
  }
}
seen; // ["a", "c", "d"]

const m = new Map<unknown, string>();
m.set(NaN, "nan").set(-0, "zero").set(1, "one");
m.get(NaN); // "nan"
m.get(0); // "zero"
Object.is([...m.keys()][1], -0); // false: stored as +0
m.get("1"); // undefined: no conversion
 
const k = [1, 2];
m.set(k, "array");
m.get([1, 2]); // undefined: another array
m.get(k); // "array": the same array
 
m.set("1,2", "pair");
m.get(`${1},${2}`); // "pair": strings match by value

const glued = (r: number, c: number) => `${r}${c}`;
glued(1, 12) === glued(11, 2); // true: "112" twice
const key = (r: number, c: number) => `${r},${c}`;
key(1, 12) === key(11, 2); // false
 
const COLS = 4;
const walls = new Set([0 * COLS + 1, 1 * COLS + 3]);
walls.has(1 * COLS + 3); // true: row 1, column 3
const cell = 7;
[Math.floor(cell / COLS), cell % COLS]; // [1, 3]

const tally: Record<string, number> = {};
for (const w of ["constructor", "a"]) {
  tally[w] = (tally[w] ?? 0) + 1;
}
typeof tally.constructor; // "string": Object's function + 1
typeof tally.a; // "number"
 
const obj: Record<number, string> = { 2: "b", 1: "a" };
Object.keys(obj); // ["1", "2"]: strings, sorted
const map = new Map([[2, "b"], [1, "a"]]);
[...map.keys()]; // [2, 1]: numbers, insertion order
JSON.stringify(map); // "{}"
JSON.stringify(Object.fromEntries(map));
// '{"1":"a","2":"b"}': an object sorts them again

const a = new Set([1, 2, 3]);
const b = new Set([3, 4]);
a.union(b); // Set(4) {1, 2, 3, 4}
a.intersection(b); // Set(1) {3}
a.difference(b); // Set(2) {1, 2}
a.symmetricDifference(b); // Set(3) {1, 2, 4}
new Set([1, 2]).isSubsetOf(a); // true
a.isDisjointFrom(b); // false: 3 is shared
 
const ids = new Map([[3, "c"], [9, "z"]]);
a.intersection(ids); // Set(1) {3}: a Map is set-like
a.union(new Set([5, 6])); // an array must be wrapped

const letters = (w: string) => {
  let m = 0;
  for (const ch of w) m |= 1 << (ch.charCodeAt(0) - 97);
  return m;
};
letters("abcab").toString(2); // "111"
(letters("abc") & letters("xyz")) === 0; // true
(letters("ab") & letters("cab")) === letters("ab");
// true: a subset
 
const popcount = (x: number) => {
  let n = 0;
  for (; x !== 0; x &= x - 1) n++;
  return n;
};
popcount(letters("hello")); // 4: h, e, l, o

const meta = new WeakMap<object, number>();
const node = { id: 1 };
meta.set(node, 42);
meta.get(node); // 42
meta.has({ id: 1 }); // false: another object
 
const sums = new WeakMap<readonly number[], number>();
function total(xs: readonly number[]): number {
  let t = sums.get(xs);
  if (t === undefined) {
    t = xs.reduce((s, x) => s + x, 0);
    sums.set(xs, t);
  }
  return t;
}
const data = [1, 2, 3];
total(data); // 6: computed
total(data); // 6: cached until data is collected

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>(); // value -> index
  for (const [i, x] of nums.entries()) {
    const j = seen.get(target - x);
    if (j !== undefined) return [j, i];
    seen.set(x, i); // after the check: no self-pairs
  }
  return [];
}
 
function subarraySum(nums: number[], k: number): number {
  const count = new Map([[0, 1]]); // the empty prefix
  let pre = 0;
  let ans = 0;
  for (const x of nums) {
    pre += x;
    ans += count.get(pre - k) ?? 0;
    count.set(pre, (count.get(pre) ?? 0) + 1);
  }
  return ans;
}
 
twoSum([3, 2, 4], 6); // [1, 2]
subarraySum([1, 1, 1], 2); // 2

function firstOf(m: Map<string, number[]>, k: string) {
  if (m.has(k)) {
    // @ts-expect-error: get() is still number[] | undefined
    return m.get(k)[0];
  }
  return undefined;
}
 
function firstOrNull(m: Map<string, number[]>, k: string) {
  const list = m.get(k); // read once
  return list ? list[0] : null; // narrowed
}
firstOrNull(new Map([["a", [7]]]), "a"); // 7

function counter<T>(xs: Iterable<T>): Map<T, number> {
  const m = new Map<T, number>();
  for (const x of xs) m.set(x, (m.get(x) ?? 0) + 1);
  return m;
}
counter("abca"); // Map(3) {"a" => 2, "b" => 1, "c" => 1}
 
class DefaultMap<K, V> extends Map<K, V> {
  readonly #make: (key: K) => V;
  constructor(make: (key: K) => V) {
    super();
    this.#make = make;
  }
  override get(key: K): V {
    let v = super.get(key);
    if (v === undefined) {
      v = this.#make(key);
      this.set(key, v);
    }
    return v;
  }
}
 
const graph = new DefaultMap<string, string[]>(() => []);
graph.get("a").push("b"); // typed string[]: no check
graph.get("c"); // [], and "c" is now a key
[...graph.keys()]; // ["a", "c"]

const nums = new Map<string, number>([["a", 1]]);
function tag(m: Map<string, number | string>) {
  m.set("note", "oops");
}
tag(nums); // compiles
typeof nums.get("note"); // "string", in a number map
 
function size(m: ReadonlyMap<string, number | string>) {
  return m.size; // nothing to write with
}
size(nums); // 2

const m = new Map<string, number>([["a", 1]]);
"a" in m; // false: checks properties, not keys
m.has("a"); // true
 
// @ts-expect-error: a Map has no index signature
m["b"] = 2;
m.size; // 1: that wrote a property, not an entry

class LRUCache<K, V> {
  readonly #cap: number;
  readonly #m = new Map<K, V>();
  constructor(capacity: number) {
    this.#cap = capacity;
  }
  get(key: K): V | undefined {
    const v = this.#m.get(key);
    if (v === undefined) return undefined;
    this.#m.delete(key); // move to the newest end
    this.#m.set(key, v);
    return v;
  }
  put(key: K, value: V): void {
    this.#m.delete(key);
    this.#m.set(key, value);
    if (this.#m.size > this.#cap) {
      const oldest = this.#m.keys().next().value!;
      this.#m.delete(oldest);
    }
  }
}
 
const cache = new LRUCache<number, number>(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 1
cache.put(3, 3); // evicts 2
cache.get(2); // undefined
cache.put(4, 4); // evicts 1
cache.get(1); // undefined
cache.get(3); // 3
cache.get(4); // 4

function groupAnagrams(words: string[]): string[][] {
  const groups = Map.groupBy(words, (w) =>
    [...w].sort().join(""),
  );
  return [...groups.values()];
}
 
groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]);
// [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

function longestRun(nums: number[]): number {
  const s = new Set(nums);
  let best = 0;
  for (const x of s) {
    if (s.has(x - 1)) continue; // not the start of a run
    let y = x;
    while (s.has(y + 1)) y++;
    best = Math.max(best, y - x + 1);
  }
  return best;
}
 
longestRun([100, 4, 200, 1, 3, 2]); // 4: 1 to 4

function topK(nums: number[], k: number): number[] {
  const count = new Map<number, number>();
  for (const x of nums) {
    count.set(x, (count.get(x) ?? 0) + 1);
  }
  // buckets[c] holds the values seen exactly c times
  const buckets: number[][] = Array.from(
    { length: nums.length + 1 },
    () => [],
  );
  for (const [x, c] of count) buckets[c]!.push(x);
  const out: number[] = [];
  for (let c = nums.length; c > 0; c--) {
    for (const x of buckets[c]!) {
      out.push(x);
      if (out.length === k) return out;
    }
  }
  return out;
}
 
topK([1, 1, 1, 2, 2, 3], 2); // [1, 2]

function firstUnique(s: string): number {
  const count = new Map<string, number>();
  for (const ch of s) {
    count.set(ch, (count.get(ch) ?? 0) + 1);
  }
  for (let i = 0; i < s.length; i++) {
    if (count.get(s[i]!) === 1) return i;
  }
  return -1;
}
 
firstUnique("leetcode"); // 0
firstUnique("loveleetcode"); // 2
firstUnique("aabb"); // -1

function nearbyDuplicate(nums: number[], k: number) {
  const lastAt = new Map<number, number>();
  for (const [i, x] of nums.entries()) {
    const j = lastAt.get(x);
    if (j !== undefined && i - j <= k) return true;
    lastAt.set(x, i);
  }
  return false;
}
 
nearbyDuplicate([1, 2, 3, 1], 3); // true
nearbyDuplicate([1, 2, 3, 1, 2, 3], 2); // false

function isomorphic(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  const st = new Map<string, string>();
  const ts = new Map<string, string>();
  for (let i = 0; i < s.length; i++) {
    const a = s[i]!;
    const b = t[i]!;
    if ((st.get(a) ?? b) !== b) return false;
    if ((ts.get(b) ?? a) !== a) return false;
    st.set(a, b);
    ts.set(b, a);
  }
  return true;
}
 
isomorphic("egg", "add"); // true
isomorphic("foo", "bar"); // false
isomorphic("badc", "baba"); // false: d and b both map to b

function isHappy(n: number): boolean {
  const seen = new Set<number>();
  while (n !== 1 && !seen.has(n)) {
    seen.add(n);
    let next = 0;
    for (; n > 0; n = Math.floor(n / 10)) {
      next += (n % 10) ** 2;
    }
    n = next;
  }
  return n === 1;
}
 
isHappy(19); // true
isHappy(2); // false

function longestKDistinct(s: string, k: number): number {
  const count = new Map<string, number>();
  let lo = 0;
  let best = 0;
  for (let hi = 0; hi < s.length; hi++) {
    const ch = s[hi]!;
    count.set(ch, (count.get(ch) ?? 0) + 1);
    while (count.size > k) {
      const gone = s[lo++]!;
      const left = count.get(gone)! - 1;
      if (left === 0) count.delete(gone); // else size lies
      else count.set(gone, left);
    }
    best = Math.max(best, hi - lo + 1);
  }
  return best;
}
 
longestKDistinct("eceba", 2); // 3: "ece"

function canBuild(note: string, letters: string): boolean {
  const have = new Map<string, number>();
  for (const ch of letters) {
    have.set(ch, (have.get(ch) ?? 0) + 1);
  }
  for (const ch of note) {
    const n = have.get(ch) ?? 0;
    if (n === 0) return false;
    have.set(ch, n - 1);
  }
  return true;
}
 
canBuild("aab", "baa"); // true
canBuild("aa", "ab"); // false