// ─────────────────────────────────────────────────────────────────────────────
// HASH MAPS
// ─────────────────────────────────────────────────────────────────────────────
// WHAT   : trade O(n) space for O(1) lookups; turn nested loops into one pass.
// TELL   : "count", "frequency", "seen before", "pairs that sum to", "group by",
//          "consecutive", "subarray sum equals", "LRU", "O(n) required".
// SAY    : hash map / hash set, frequency map, complement lookup, prefix-sum map,
//          bucket sort by frequency, chaining, load factor, rehash, Map insertion order.
// BIG-O  : O(1) average per op; O(n) worst case (all keys collide).
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

// ── 1. Frequency counting idiom  —  map.set(k, (map.get(k) ?? 0) + 1)  —  O(n) / O(k)
function freq(iter) {
  const m = new Map();
  for (const x of iter) m.set(x, (m.get(x) ?? 0) + 1);
  return m;
}
assert.deepEqual([...freq('aabc')], [['a', 2], ['b', 1], ['c', 1]]);
assert.deepEqual([...freq([])], []);

// ── 2. Two-sum  —  complement lookup; one pass  —  O(n) / O(n)
function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (seen.has(target - nums[i])) return [seen.get(target - nums[i]), i];
    seen.set(nums[i], i);
  }
  return [];
}
assert.deepEqual(twoSum([2, 7, 11, 15], 9), [0, 1]);
assert.deepEqual(twoSum([-1, -2, -3], -5), [1, 2]);
assert.deepEqual(twoSum([], 1), []);

// ── 3. Group anagrams  —  key = count signature (26 ints joined) avoids sorting  —  O(nk) / O(nk)
function groupAnagrams(strs) {
  const g = new Map();
  for (const w of strs) {
    const cnt = new Array(26).fill(0);
    for (const c of w) cnt[c.charCodeAt(0) - 97]++;
    const key = cnt.join('#');
    if (!g.has(key)) g.set(key, []);
    g.get(key).push(w);
  }
  return [...g.values()];
}
assert.deepEqual(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']), [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]);
assert.deepEqual(groupAnagrams([]), []);

// ── 4. Longest consecutive sequence  —  Set; only start counting from x when x-1 absent  —  O(n) / O(n)
function longestConsecutive(nums) {
  const set = new Set(nums);
  let best = 0;
  for (const x of set) {
    if (set.has(x - 1)) continue; // not a sequence start
    let len = 1;
    while (set.has(x + len)) len++;
    best = Math.max(best, len);
  }
  return best;
}
assert.equal(longestConsecutive([100, 4, 200, 1, 3, 2]), 4);
assert.equal(longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]), 9);
assert.equal(longestConsecutive([]), 0);

// ── 5. Subarray sum equals k (count)  —  prefix-sum map: count[pre - k]; seed {0:1}  —  O(n) / O(n)
function subarraySum(nums, k) {
  const count = new Map([[0, 1]]);
  let pre = 0, total = 0;
  for (const x of nums) {
    pre += x;
    total += count.get(pre - k) ?? 0;
    count.set(pre, (count.get(pre) ?? 0) + 1);
  }
  return total;
}
assert.equal(subarraySum([1, 1, 1], 2), 2);
assert.equal(subarraySum([1, 2, 3], 3), 2);
assert.equal(subarraySum([1, -1, 0], 0), 3); // negatives OK (sliding window would NOT be)

// ── 6. Contains duplicate within distance k  —  map value -> last index  —  O(n) / O(n)
function containsNearbyDuplicate(nums, k) {
  const last = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (last.has(nums[i]) && i - last.get(nums[i]) <= k) return true;
    last.set(nums[i], i);
  }
  return false;
}
assert.equal(containsNearbyDuplicate([1, 2, 3, 1], 3), true);
assert.equal(containsNearbyDuplicate([1, 2, 3, 1, 2, 3], 2), false);
assert.equal(containsNearbyDuplicate([], 1), false);

// ── 7. LRU cache via Map insertion order  —  get: delete + re-set moves to end; evict map.keys().next().value  —  O(1) / O(cap)
class LRUCache {
  #cap; #m = new Map();
  constructor(capacity) { this.#cap = capacity; }
  get(key) {
    if (!this.#m.has(key)) return -1;
    const v = this.#m.get(key);
    this.#m.delete(key); this.#m.set(key, v); // refresh recency
    return v;
  }
  put(key, value) {
    if (this.#m.has(key)) this.#m.delete(key);
    this.#m.set(key, value);
    if (this.#m.size > this.#cap) this.#m.delete(this.#m.keys().next().value); // oldest = first key
  }
}
const lru = new LRUCache(2);
lru.put(1, 1); lru.put(2, 2);
assert.equal(lru.get(1), 1);
lru.put(3, 3); // evicts 2
assert.equal(lru.get(2), -1);
assert.equal(lru.get(3), 3);

// ── 8. First non-repeating character  —  freq pass + order pass (Map keeps insertion order)  —  O(n) / O(k)
function firstNonRepeating(s) {
  const f = freq(s);
  for (const [c, n] of f) if (n === 1) return c;
  return null;
}
assert.equal(firstNonRepeating('swiss'), 'w');
assert.equal(firstNonRepeating('aabb'), null);
assert.equal(firstNonRepeating(''), null);

// ── 9. Intersection of two arrays (unique)  —  Set of a, filter b, dedupe  —  O(n+m) / O(n)
function intersection(a, b) {
  const sa = new Set(a);
  return [...new Set(b.filter((x) => sa.has(x)))];
}
assert.deepEqual(intersection([1, 2, 2, 1], [2, 2]), [2]);
assert.deepEqual(intersection([4, 9, 5], [9, 4, 9, 8, 4]), [9, 4]);
assert.deepEqual(intersection([], [1]), []);

// ── 10. Top-k frequent elements (bucket sort variant)  —  bucket[count] = [values]; walk from high count  —  O(n) / O(n)
function topKFrequent(nums, k) {
  const f = freq(nums);
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [v, c] of f) buckets[c].push(v);
  const out = [];
  for (let c = buckets.length - 1; c >= 0 && out.length < k; c--) out.push(...buckets[c]);
  return out.slice(0, k);
}
assert.deepEqual(topKFrequent([1, 1, 1, 2, 2, 3], 2), [1, 2]);
assert.deepEqual(topKFrequent([1], 1), [1]);
assert.deepEqual(topKFrequent([], 1), []);

// ── 11. Design a HashMap (buckets + chaining)  —  hash(key) % buckets; each bucket is a list of [k,v]
//        SAY: collision -> chaining (lists) or open addressing (linear probing);
//             load factor = size / buckets; rehash (double buckets) when > ~0.75 keeps O(1) amortized.
class MyHashMap {
  #buckets; #size = 0;
  constructor(n = 16) { this.#buckets = Array.from({ length: n }, () => []); }
  #hash(key) {
    let h = 0;
    for (const c of String(key)) h = (h * 31 + c.charCodeAt(0)) | 0;
    return Math.abs(h) % this.#buckets.length;
  }
  put(key, value) {
    const b = this.#buckets[this.#hash(key)];
    const e = b.find((p) => p[0] === key);
    if (e) e[1] = value;
    else { b.push([key, value]); this.#size++; }
    if (this.#size / this.#buckets.length > 0.75) this.#rehash();
  }
  get(key) { return this.#buckets[this.#hash(key)].find((p) => p[0] === key)?.[1] ?? -1; }
  remove(key) {
    const b = this.#buckets[this.#hash(key)];
    const i = b.findIndex((p) => p[0] === key);
    if (i >= 0) { b.splice(i, 1); this.#size--; }
  }
  #rehash() {
    const old = this.#buckets.flat();
    this.#buckets = Array.from({ length: this.#buckets.length * 2 }, () => []);
    this.#size = 0;
    for (const [k, v] of old) this.put(k, v);
  }
  get size() { return this.#size; }
}
const hm = new MyHashMap(2); // tiny so rehash actually triggers
for (let i = 0; i < 20; i++) hm.put(i, i * i);
assert.equal(hm.get(7), 49);
assert.equal(hm.get(99), -1);
hm.remove(7);
assert.equal(hm.get(7), -1);
assert.equal(hm.size, 19);

console.log('ok: algorithms/hash-maps.js');