Hashing — Complete Guide with Interactive Walkthroughs

If you could only master one data structure for coding interviews, make it the hash map. Hash maps (and their sibling sets) give you O(1) average-time add, remove, and lookup — turning nested O(n²) loops into single-pass O(n) algorithms over and over again.

This guide follows the same format as [Two Pointers](/blog/two-pointers-technique), [Sliding Window](/blog/sliding-window-technique), and [Prefix Sum](/blog/prefix-sum-technique): core concepts, interactive walkthroughs, code in three languages, and a practice ladder. Focus on the interface — how to use built-in maps and sets — not implementing hash tables from scratch.

---

Interface vs Implementation

A data structure has two parts:

• Interface — what operations you can perform and what they return (set, get, has, delete)
• Implementation — how it works under the hood (hash function, collision handling, resizing)

In interviews you use the built-in hash map of your language. You won't be asked to implement one — but you should know what it gives you: key → value storage with fast lookup.

Keys must be immutable (or hashable). Arrays are mutable — convert to a tuple, sorted string, or delimited string before using as a key.

---

What Is Hashing?

A hash function converts any input (string, number, object) into an integer within a fixed range. The same key always maps to the same bucket.

key  →  hash(key) % tableSize  →  bucket index

Combined with an array, this creates a hash map: map keys to values without requiring integer indices.

Hash map — stores key-value pairs. Duplicate keys overwrite.

Hash set — stores keys only (no values). Adding the same element twice does nothing.

Five patterns cover most interview problems:

---

Hash Map vs Array

Tradeoffs: Hash maps have constant-factor overhead and can use more memory. For tiny inputs, a plain array scan can be faster. For unknown key ranges (e.g. value 999999999), a hash map is safer than sizing a giant array.

Note: "O(1) hash map operations" are O(1) relative to map size n. Hashing a string of length m costs O(m).

---

Pattern 1 — Checking for Existence

Anytime you write if (x in arr) inside a loop, consider a set or map for O(1) lookup.

Example 1 — Two Sum

[LeetCode 1. Two Sum](https://leetcode.com/problems/two-sum/)

Given nums and target, return indices of two numbers that add to target.

Brute force: nested loops → O(n²).

Hash map: at index i, check if target - nums[i] is already in the map. Store nums[i] → i as you go.

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 [];
}

twoSum([2, 7, 11, 15], 9); // [0, 1]

Why a map, not a set? We need indices, not just whether a pair exists.

Complexity: O(n) time, O(n) space.

---

Example 2 — First Letter to Appear Twice

[LeetCode 2351](https://leetcode.com/problems/first-letter-to-appear-twice/)

Return the first character in s that appears twice.

Brute force: for each position, scan earlier characters → O(n²).

Set: if c is already in the set, return c. Otherwise add it.

function repeatedCharacter(s) {
  const seen = new Set();
  for (const c of s) {
    if (seen.has(c)) return c;
    seen.add(c);
  }
  return "";
}

repeatedCharacter("abccba"); // "c"

Space: O(m) where m is the number of possible characters (26 for lowercase English — often called O(1) in interviews).

---

Example 3 — Isolated Numbers

Return all x in nums where neither x + 1 nor x - 1 exists in nums. Each valid x appears once in the answer.

Pre-process nums into a set, then check neighbors in O(1) per element.

function findIsolated(nums) {
  const set = new Set(nums);
  const ans = [];
  for (const x of nums) {
    if (!set.has(x + 1) && !set.has(x - 1) && !ans.includes(x)) {
      ans.push(x);
    }
  }
  return ans;
}

findIsolated([1, 2, 3, 5, 8]); // [5, 8]

Rule of thumb: if (... in ...) inside a loop → try a hash set or map.

---

Pattern 2 — Counting Frequencies

Use a map key → count whenever you need to track how often something appears.

Example 4 — At Most K Distinct Characters

Given string s and integer k, find the length of the longest substring with at most k distinct characters.

This is a sliding window problem — but the constraint involves multiple characters, so an integer counter isn't enough. Use counts: Map.

• counts.size = number of distinct characters in the window
• Shrink from the left when counts.size > k

function longestKDistinct(s, k) {
  const counts = new Map();
  let left = 0;
  let best = 0;

  for (let right = 0; right < s.length; right++) {
    counts.set(s[right], (counts.get(s[right]) ?? 0) + 1);

    while (counts.size > k) {
      const c = s[left];
      counts.set(c, counts.get(c) - 1);
      if (counts.get(c) === 0) counts.delete(c);
      left++;
    }

    best = Math.max(best, right - left + 1);
  }

  return best;
}

longestKDistinct("eceba", 2); // 3

Complexity: O(n) time, O(k) space for the map.

---

Example 5 — Intersection of Multiple Arrays

[LeetCode 2248](https://leetcode.com/problems/intersection-of-multiple-arrays/)

Each inner array has distinct integers. Return sorted numbers that appear in all arrays.

A number appears in all n arrays ⟺ its count equals n.

function intersection(nums) {
  const n = nums.length;
  const counts = new Map();
  for (const arr of nums) {
    for (const x of arr) {
      counts.set(x, (counts.get(x) ?? 0) + 1);
    }
  }
  const ans = [];
  for (const [x, c] of counts) {
    if (c === n) ans.push(x);
  }
  return ans.sort((a, b) => a - b);
}

intersection([[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]); // [3, 4]

Why not an array? If max element is 1000, you'd need a size-1001 array mostly empty. A hash map handles sparse keys efficiently.

---

Example 6 — Equal Character Frequencies

[LeetCode 1941](https://leetcode.com/problems/check-if-all-characters-have-equal-number-of-occurrences/)

Return true if every character in s appears the same number of times.

Count frequencies in a map, put all counts in a set, check set.size === 1.

function areOccurrencesEqual(s) {
  const counts = new Map();
  for (const c of s) counts.set(c, (counts.get(c) ?? 0) + 1);
  return new Set(counts.values()).size === 1;
}

areOccurrencesEqual("abacbc"); // true
areOccurrencesEqual("aaabb");  // false

---

Pattern 3 — Prefix Sum + Frequency Map

For exact subarray constraints (sum = K, exactly K odds), sliding window alone isn't enough. Combine prefix sums with a hash map counting how often each prefix has appeared.

Key idea: at index i, curr = prefix sum up to i. A subarray ending at i with sum k exists iff prefix curr - k was seen before.

ans += counts[curr - k]
counts[curr]++

Always initialize counts[0] = 1 (empty prefix).

Example 7 — Subarray Sum Equals K

[LeetCode 560](https://leetcode.com/problems/subarray-sum-equals-k/)

function subarraySum(nums, k) {
  const counts = new Map([[0, 1]]);
  let curr = 0;
  let ans = 0;

  for (const num of nums) {
    curr += num;
    ans += counts.get(curr - k) ?? 0;
    counts.set(curr, (counts.get(curr) ?? 0) + 1);
  }

  return ans;
}

subarraySum([1, 2, 1, 2, 1], 3); // 4

Why a map, not a set? With negative numbers, the same prefix sum can occur multiple times — each occurrence is a valid start point.

Complexity: O(n) time and space.

---

Example 8 — Count Nice Subarrays (Exactly K Odds)

[LeetCode 1248](https://leetcode.com/problems/count-number-of-nice-subarrays/)

Count subarrays with exactly k odd numbers. Same pattern — but curr tracks odd count instead of sum:

curr += num % 2;
ans += counts.get(curr - k) ?? 0;

The code differs by literally % 2 from the sum version.

---

Pattern 4 — Grouping by Signature

When items belong to the same group if they share a property (anagrams, digit sum, row pattern), use a canonical key:

Example 9 — Group Anagrams

[LeetCode 49](https://leetcode.com/problems/group-anagrams/)

function groupAnagrams(strs) {
  const groups = new Map();
  for (const word of strs) {
    const key = [...word].sort().join("");
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }
  return [...groups.values()];
}

groupAnagrams(["eat","tea","tan","ate","nat","bat"]);
// [["eat","tea","ate"], ["tan","nat"], ["bat"]]

Alternative key: length-26 frequency tuple — O(n·m) vs O(n·m log m) for sorting.

---

Example 10 — Shortest Subarray With Duplicate

[LeetCode 2260](https://leetcode.com/problems/minimum-consecutive-cards-to-pick-up/)

Find shortest subarray containing a duplicate. Track most recent index per value — only store the last index, not all indices.

function minimumCardPickup(cards) {
  const last = new Map();
  let best = Infinity;

  for (let i = 0; i < cards.length; i++) {
    if (last.has(cards[i])) {
      best = Math.min(best, i - last.get(cards[i]) + 1);
    }
    last.set(cards[i], i);
  }

  return best === Infinity ? -1 : best;
}

minimumCardPickup([1, 2, 6, 2, 1]); // 3

---

Example 11 — Equal Row and Column Pairs

[LeetCode 2352](https://leetcode.com/problems/equal-row-and-column-pairs/)

Count pairs (R, C) where row R equals column C as 1D arrays. Convert rows/columns to immutable tuple keys (string or joined values), count occurrences, multiply matching counts.

Complexity: O(n²) for an n×n grid.

---

Complexity Cheat Sheet

---

Common Mistakes

Using an array when keys are sparse. [1, 2, 1000] doesn't mean you need an array of size 1000.

Forgetting counts[0] = 1 in prefix-frequency problems — you lose subarrays that start at index 0.

Using a set when you need frequencies. Duplicate prefix sums require counting, not just existence.

Mutable keys. Don't use arrays as map keys directly — sort/join/tuple first.

Assuming hash map order. Iteration order is not sorted (in most languages).

Ignoring O(m) string hashing. Hashing a string of length m is not O(1).

---

Practice Problems (Easiest → Hardest)

---

Quick Reference — Pattern Picker

---

Key Takeaways

1. Hash map = O(1) lookup — the single biggest time-complexity upgrade in interviews.
2. if (x in arr) in a loop → use a set or map.
3. Count frequencies with map[key]++ — windows, intersections, anagrams.
4. Two Sum pattern: search for target - num, not pairs of loops.
5. Prefix + freq map: counts[curr - k] counts exact subarray constraints.
6. Group by signature: sorted string, digit sum, or tuple as map key.
7. Sets don't track frequency — adding the same key 100 times still yields size 1.
8. Step through the animations — if you can narrate each map update, you can code it.

Hash maps appear in almost every topic from here on. Pair this guide with [Prefix Sum](/blog/prefix-sum-technique) for the prefix-frequency pattern, and [Sliding Window](/blog/sliding-window-technique) when the constraint lives inside a contiguous window.