Hash Map / Set

Hash maps (dictionaries) and sets are the most versatile data structures in coding interviews. They give you O(1) average time for insert, delete, and lookup operations.

Think of a hash map as a super-powered array where you can use ANY value as an index, not just integers 0 to n-1. Instead of array[5], you can do map['hello'] or map[someObject].

When to immediately think 'hash map':

• •'Find if X exists' -> Set for O(1) lookup
• •'Find pair that sums to target' -> Map to store complements
• •'Count occurrences' -> Map as frequency counter
• •'Group items by property' -> Map with computed key
• •'Check for duplicates' -> Set

The pattern recognition is crucial: whenever you see O(n²) nested loops checking 'have I seen this before?', a hash map can often reduce it to O(n).

Two Sum is THE classic hash map problem. Given an array and a target sum, find two numbers that add up to the target.

The brute force approach checks every pair: O(n²). But with a hash map, we can do it in O(n).

The key insight: for each number X, we need to find if (target - X) exists. Instead of scanning the array each time, store what we've seen in a hash map.

Critical detail: Check for complement BEFORE adding current number to the map. Otherwise, you might match an element with itself.

This pattern extends to:

• •3Sum, 4Sum (combine with two pointers)
• •Finding pairs with any relationship (difference, product)
• •Subarray sum problems (using prefix sums)

Many problems require counting how often elements appear. A hash map is perfect for this.

Building a frequency map:

1. •Iterate through elements
2. •For each element, increment its count in the map
3. •Use getOrDefault (Java) or || 0 (JS) for elements not yet seen

Pro tip for characters: When counting lowercase letters, use an int[26] array instead of a hash map. It's faster and uses less memory. The index is calculated as: char - 'a'.

This pattern is the foundation for:

• •Top K Frequent Elements
• •Valid Anagram
• •First Unique Character
• •Majority Element
• •Sort Characters by Frequency

Sometimes you need to group elements that share a common property. The key insight is choosing the RIGHT key for your hash map.

For Group Anagrams, all anagrams share the same letters - just in different order. So we need a 'canonical form' that's the same for all anagrams:

Option 1: Sort the string

• •'eat', 'tea', 'ate' all become 'aet'
• •Simple but O(k log k) per string where k is string length

Option 2: Character count as key

• •'eat' -> '#1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0'
• •O(k) per string, but longer key

This pattern works for any grouping problem:

• •Group by pattern (Word Pattern)
• •Group by transformation (Isomorphic Strings)
• •Group by any computed property

This problem showcases the power of Set for O(1) lookups. Find the length of the longest consecutive sequence in an unsorted array.

Brute force: Sort the array first, then scan for consecutive runs. O(n log n).

Hash Set approach: O(n) time!

The trick: Only start counting from the BEGINNING of a sequence. How do we know if a number starts a sequence? Check if (num - 1) exists - if not, this number is a sequence start.

For each sequence start, keep checking if (num + 1), (num + 2), etc. exist. This looks like O(n²), but each number is only visited once as part of exactly one sequence, so it's O(n) total.

Sets are perfect for tracking what you've seen. The add() operation returns false if the element already exists - a one-liner for duplicate detection!

Contains Duplicate: Does any value appear twice?

• •Add each element to a set
• •If add() returns false (already exists), we found a duplicate

Contains Duplicate II: Are there duplicates within k indices of each other?

• •Store index in a map, or use a sliding window set of size k

Find All Duplicates: Which values appear exactly twice? (Array values are 1 to n)

• •Clever trick: Use the array itself as a hash map
• •For value v, mark index (v-1) as negative
• •If already negative, v is a duplicate

Sets give you O(1) membership testing, making intersection and union operations efficient.

Intersection of Two Arrays:

1. •Put all elements of array1 into a Set
2. •For each element in array2, check if it's in the Set
3. •If yes, add to result (use another Set to avoid duplicates)

Happy Number (uses Set for cycle detection): A number is 'happy' if repeatedly summing squares of its digits eventually reaches 1. If it loops forever, it's not happy.

Use a Set to detect cycles - if we see the same number twice, we're in a loop.

Quick reference for which hash structure to use:

Common pitfalls:

• •HashMap operations are O(1) average but O(n) worst case (hash collisions)
• •Custom objects as keys need proper hashCode() and equals()
• •In JavaScript, objects as Map keys use reference equality
• •Sets don't maintain order (use LinkedHashSet if needed)

Find the first non-repeating character in a string. A perfect frequency counting problem.

Two-Pass Approach:

1. •First pass: Count frequency of each character
2. •Second pass: Return first character with count = 1

Example: "leetcode"

Example: "loveleetcode"

Why Two Passes? We can't return on first occurrence because we don't know if it repeats later. We need full frequency information before deciding.

Check if a 9x9 Sudoku board is valid. Use sets to track what we've seen in each row, column, and 3x3 box.

The Key Insight: We need to check three constraints simultaneously:

1. •Each row contains 1-9 with no duplicates
2. •Each column contains 1-9 with no duplicates
3. •Each 3x3 box contains 1-9 with no duplicates

Box Index Formula: For cell at (row, col), box index = (row / 3) * 3 + (col / 3)

Encoding Trick: Instead of 27 separate sets, use one set with encoded strings:

• •"row 0 has 5"
• •"col 3 has 5"
• •"box 4 has 5"

Check if two sequences follow the same pattern - a bijection (one-to-one mapping) problem.

Word Pattern: Does "dog cat cat dog" match pattern "abba"? Isomorphic Strings: Does "egg" map to "add"?

Key Insight: We need BIDIRECTIONAL mapping:

• •Each pattern char maps to exactly one word
• •Each word maps to exactly one pattern char

Example: pattern="abba", s="dog cat cat dog"

Example: pattern="abba", s="dog cat cat fish"

Why Two Maps? With only pattern→word, "abba" would incorrectly match "dog dog dog dog" (a→dog, b→dog both work one-way but violate bijection).

Count subarrays with sum exactly K. This combines prefix sum with HashMap lookup.

The Brilliant Insight: If prefix[j] - prefix[i] = k, then subarray [i+1, j] has sum k.

Rearranging: prefix[i] = prefix[j] - k

So for each position j, we ask: "How many earlier prefix sums equal (currentSum - k)?"

Visual Trace: nums = [1, 2, 3], k = 3

Critical: Initialize with {0: 1} to count subarrays starting at index 0.

Design a Least Recently Used (LRU) cache with O(1) get and put operations.

Requirements:

• •get(key): Return value if exists, mark as recently used
• •put(key, value): Add/update, evict LRU item if at capacity

Data Structure: Combine HashMap (O(1) lookup) + Doubly Linked List (O(1) reorder):

• •HashMap: key → Node
• •DLL: maintains usage order (head = most recent, tail = LRU)

Operations:

Java Shortcut: LinkedHashMap with accessOrder=true does this automatically!

Find the k most frequent elements. Combines frequency counting with selection.

Three Approaches:

1. Heap Approach - O(n log k)

• •Build frequency map
• •Use min-heap of size k
• •Keep k most frequent

2. Bucket Sort - O(n)

• •Build frequency map
• •Create buckets where index = frequency
• •Collect from highest buckets

3. Quick Select - O(n) average

• •Similar to finding kth element
• •More complex to implement

Bucket Sort Visualization:

Can we construct ransom note from magazine letters? A simple frequency comparison.

Algorithm:

1. •Count letter frequencies in magazine
2. •For each letter in ransom note, decrement count
3. •If any count goes negative, return false

Optimization: Use int[26] instead of HashMap for lowercase letters.

Example:

Quick reference for HashMap/Set problems:

Decision Tree:

Mistake 1: Forgetting Initialization

Mistake 2: Modifying While Iterating

Mistake 3: Using Mutable Objects as Keys

Mistake 4: Not Using getOrDefault

Pro Tips:

1. •For character counting, prefer int[26] over HashMap
2. •Use merge() for frequency counting: map.merge(key, 1, Integer::sum)
3. •JavaScript Map preserves insertion order (useful for LRU)
4. •Check for null/undefined before calling methods on map values

Time Complexity:

Worst Case: HashMap operations can be O(n) with bad hash function (all collisions). Java 8+ uses trees for buckets with many collisions, improving to O(log n).

Space Complexity:

• •HashMap: O(n) for n entries
• •int[26]: O(1) for character counting
• •LinkedHashMap: O(n) with extra pointer overhead

When to Use What:

Memory Comparison (approximate):

Template 1: Frequency Counter

Template 2: Two Sum / Complement Lookup

Template 3: Grouping

Template 4: Character Frequency (Optimized)

Template 5: Sliding Window with Set

Template 6: Bidirectional Mapping