Hash Sets

// ===== The model =====
// HashSet:  store unique items, fast 'contains'
// HashMap:  key -> value, fast 'get / set'
// Both rely on a HASH function distributing keys evenly across buckets.

// ===== Average complexity =====
// Insert / Lookup / Delete: O(1) amortised
// Worst case: O(n) under collisions (rare with a good hash + low load factor)

// ===== JavaScript Sets and Maps =====
const seen = new Set();
seen.add(1); seen.add(2); seen.add(1);
seen.has(1);                   // true
seen.size;                     // 2
seen.delete(2);

const m = new Map();
m.set('alex', 30);
m.set('sam', 25);
m.get('alex');                  // 30
m.has('alex');                  // true
m.size;                         // 2

// ===== The most common interview pattern =====
// Two-sum: find indices i, j such that nums[i] + nums[j] == target
function twoSum(nums, target) {
  const seen = new Map();
  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);
  }
  return [];
}
// O(n) time vs O(n^2) for nested loops.

// ===== Group anagrams =====
function groupAnagrams(words) {
  const m = new Map();
  for (const w of words) {
    const key = [...w].sort().join('');
    if (!m.has(key)) m.set(key, []);
    m.get(key).push(w);
  }
  return [...m.values()];
}

// ===== First non-repeating character =====
function firstUnique(s) {
  const counts = new Map();
  for (const ch of s) counts.set(ch, (counts.get(ch) ?? 0) + 1);
  for (let i = 0; i < s.length; i++) {
    if (counts.get(s[i]) === 1) return i;
  }
  return -1;
}

// ===== When NOT to use a hash set =====
// - You need ordered traversal (use TreeSet / SortedSet)
// - Hash function is expensive (BigInt keys, complex objects)
// - Adversarial inputs (hashes are pseudo-random per process; tests should not rely on order)

// ===== Implementing 'unique' efficiently =====
// Convert array to set; back to array:
const unique = [...new Set([1, 2, 2, 3, 3, 3])];   // [1, 2, 3]

// ===== Set algebra =====
const a = new Set([1, 2, 3]);
const b = new Set([3, 4]);

// Union:
const u = new Set([...a, ...b]);
// Intersection:
const i = new Set([...a].filter(x => b.has(x)));
// Difference:
const d = new Set([...a].filter(x => !b.has(x)));

// (Modern ES2025 adds Set.prototype.union / intersection / difference natively.)

// ===== Custom objects as keys (the gotcha) =====
const m2 = new Map();
m2.set({ id: 1 }, 'a');
m2.get({ id: 1 });          // undefined (different object reference)

// Use a primitive key (id, JSON.stringify) or a custom hash.

// ===== Patterns to internalise =====
// - Hash set / map for any 'have we seen this?' or 'lookup by key' problem
// - Replace nested loops with hash lookups when possible
// - Build counts maps for frequency problems
// - Sort + hash key for grouping by 'equivalence'

// ===== Pitfalls =====
// - Object keys compared by reference, not value (JS Map)
// - Iteration order: insertion order in JS Map/Set (helpful), undefined in Python set
// - Hash collisions on adversarial inputs (DoS risk with string keys)
// - Mutating the key after insertion -> lost entry

function hasDup(nums) {
    const seen = new Set();
    for (const n of nums) {
        if (seen.has(n)) return true;
        seen.add(n);
    }
    return false;
}