Hashing — The Complete Guide

function complementLookup(arr: number[], target: number): Result {
  const map = new Map<number, number>(); // value → index (or count)

  for (let i = 0; i < arr.length; i++) {
    const complement = target - arr[i];

    if (map.has(complement)) {
      // Found a match — return indices, pair, etc.
      return [map.get(complement)!, i];
    }

    // Store current element for future lookups
    map.set(arr[i], i);
  }

  return notFound;
}
// When to use: Two Sum, pair with given difference,
// check if any two elements satisfy a condition

function frequencyCounter(arr: number[]): Map<number, number> {
  const freq = new Map<number, number>();

  for (const val of arr) {
    freq.set(val, (freq.get(val) ?? 0) + 1);
  }

  // Use the frequency map:
  // - Find duplicates: any value with freq > 1
  // - Find unique: any value with freq === 1
  // - Find most frequent: max value in the map
  // - Compare distributions: compare two frequency maps

  return freq;
}
// When to use: contains duplicate, first unique character,
// valid anagram, top K frequent, majority element,
// ransom note, sort by frequency

function groupByKey(items: string[]): Map<string, string[]> {
  const groups = new Map<string, string[]>();

  for (const item of items) {
    // Generate a canonical key for this item
    const key = generateKey(item);

    if (!groups.has(key)) {
      groups.set(key, []);
    }
    groups.get(key)!.push(item);
  }

  return groups;
}

// Key design examples:
// Group Anagrams: key = sorted characters → "eat" → "aet"
// Group by pattern: key = character mapping → "abb" → "0.1.1"
// Group by frequency: key = frequency signature → "aab" → "a2b1"

// When to use: group anagrams, isomorphic strings,
// word pattern, find all duplicates

function subarraySumEqualsK(arr: number[], k: number): number {
  const prefixCount = new Map<number, number>();
  prefixCount.set(0, 1); // empty prefix has sum 0

  let currentSum = 0;
  let count = 0;

  for (const val of arr) {
    currentSum += val;

    // If (currentSum - k) was a previous prefix sum,
    // then the subarray between them sums to k
    if (prefixCount.has(currentSum - k)) {
      count += prefixCount.get(currentSum - k)!;
    }

    prefixCount.set(currentSum, (prefixCount.get(currentSum) ?? 0) + 1);
  }

  return count;
}
// When to use: subarray sum equals k, longest subarray with sum k,
// contiguous array (equal 0s and 1s), subarrays divisible by k

function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();

  for (const s of strs) {
    // Canonical key: sort the characters
    const key = s.split("").sort().join("");

    if (!groups.has(key)) {
      groups.set(key, []);
    }
    groups.get(key)!.push(s);
  }

  return Array.from(groups.values());
}
// "eat" → "aet", "tea" → "aet", "ate" → "aet" → all grouped together
// Time: O(n × k log k) where k = max string length (sorting each string)
// Space: O(n × k) for the map

// Alternative key (avoids sorting): frequency count string
// "eat" → "1a1e1t" or use a 26-length array as key
// This gives O(n × k) time instead of O(n × k log k)

function longestConsecutive(nums: number[]): number {
  const numSet = new Set(nums);
  let longest = 0;

  for (const num of numSet) {
    // Only start counting from the BEGINNING of a sequence
    if (!numSet.has(num - 1)) {
      let current = num;
      let streak = 1;

      while (numSet.has(current + 1)) {
        current++;
        streak++;
      }

      longest = Math.max(longest, streak);
    }
  }

  return longest;
}
// Time: O(n) — each element is visited at most twice
//   (once in the outer loop, once in a while loop)
// Space: O(n) for the set
// Key insight: the "if (!numSet.has(num - 1))" check ensures
// we only start counting from sequence beginnings, avoiding
// redundant work.

function subarraySum(nums: number[], k: number): number {
  // Map: prefix sum → how many times this sum has occurred
  const prefixCount = new Map<number, number>();
  prefixCount.set(0, 1); // empty prefix (sum = 0) occurs once

  let currentSum = 0;
  let count = 0;

  for (const num of nums) {
    currentSum += num;

    // How many previous prefix sums equal (currentSum - k)?
    // Each one represents a subarray that sums to k
    const target = currentSum - k;
    if (prefixCount.has(target)) {
      count += prefixCount.get(target)!;
    }

    // Record current prefix sum
    prefixCount.set(currentSum, (prefixCount.get(currentSum) ?? 0) + 1);
  }

  return count;
}
// Time: O(n) — single pass with O(1) map operations
// Space: O(n) — storing prefix sums
// Why prefixCount.set(0, 1)? Because if currentSum itself equals k,
// the subarray from index 0 to current index is valid.
// We need (currentSum - k = 0) to be found in the map.

Input: nums = [2, 7, 11, 15], target = 9
Map: value → index

Step 1: i=0, nums[0]=2
  complement = 9 - 2 = 7
  map.has(7)? NO
  map.set(2, 0)         map = {2: 0}

Step 2: i=1, nums[1]=7
  complement = 9 - 7 = 2
  map.has(2)? YES → index 0
  Return [0, 1] ✓

Answer: [0, 1]

Key observations:
- We check BEFORE we insert — this prevents using the same element twice
- The map stores value → index, so we can return indices directly
- We only need one pass — the complement is always a previously seen element

Input: ["eat", "tea", "tan", "ate", "nat", "bat"]

Step 1: "eat" → sort → "aet"   groups = {"aet": ["eat"]}
Step 2: "tea" → sort → "aet"   groups = {"aet": ["eat", "tea"]}
Step 3: "tan" → sort → "ant"   groups = {"aet": ["eat", "tea"], "ant": ["tan"]}
Step 4: "ate" → sort → "aet"   groups = {"aet": ["eat", "tea", "ate"], "ant": ["tan"]}
Step 5: "nat" → sort → "ant"   groups = {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}
Step 6: "bat" → sort → "abt"   groups = {..., "abt": ["bat"]}

Answer: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Key: The sorted string is the canonical key.
All anagrams produce the same sorted key → they land in the same group.

Input: nums = [1, 2, 3, -2, 5], k = 3
prefixCount = {0: 1}  (empty prefix)
currentSum = 0, count = 0

Step 1: num=1, currentSum=1
  target = 1 - 3 = -2    prefixCount.has(-2)? NO
  prefixCount = {0:1, 1:1}

Step 2: num=2, currentSum=3
  target = 3 - 3 = 0     prefixCount.has(0)? YES → count += 1  (subarray [1,2,3]? No — [1,2])
  Wait — subarray from index 0 to 1 = [1,2] sums to 3 ✓
  count = 1
  prefixCount = {0:1, 1:1, 3:1}

Step 3: num=3, currentSum=6
  target = 6 - 3 = 3     prefixCount.has(3)? YES → count += 1
  Subarray: prefix 6 - prefix 3 = subarray [3] at index 2 ✓
  count = 2
  prefixCount = {0:1, 1:1, 3:1, 6:1}

Step 4: num=-2, currentSum=4
  target = 4 - 3 = 1     prefixCount.has(1)? YES → count += 1
  Subarray: prefix 4 - prefix 1 = subarray [2,3,-2] sums to 3 ✓
  count = 3
  prefixCount = {0:1, 1:1, 3:1, 6:1, 4:1}

Step 5: num=5, currentSum=9
  target = 9 - 3 = 6     prefixCount.has(6)? YES → count += 1
  Subarray: prefix 9 - prefix 6 = subarray [-2,5] sums to 3 ✓
  count = 4
  prefixCount = {0:1, 1:1, 3:1, 6:1, 4:1, 9:1}

Answer: 4

Key insight: prefixCount.set(0, 1) handles the case where
currentSum itself equals k (the subarray starts from index 0).

Does the problem involve finding a pair/complement?
├── YES → Complement Lookup (Template 1)
│         Store values; check if (target - current) exists
└── NO  → Do you need to count frequencies or find duplicates?
          ├── YES → Frequency Counter (Template 2)
          │         Count occurrences; query for most/least frequent
          └── NO  → Do you need to group equivalent items?
                    ├── YES → Grouping by Key (Template 3)
                    │         Design canonical key; map key → list of items
                    └── NO  → Do you need subarray sums?
                              ├── YES → Prefix Sum + Hash Map (Template 4)
                              │         Store prefix sums; check (currentSum - k)
                              └── NO  → Do you just need existence checks?
                                        ├── YES → Hash Set
                                        │         O(1) membership testing
                                        └── NO  → Hashing probably isn't the primary pattern
                                                  → Consider Sorting, Sliding Window, or DP