Pattern 03: Hashing / Frequency Maps

0. The Template (Copy-Paste Skeleton)

Three skeletons cover nearly every hashing problem: count, seen-before, and prefix-sum + map.

// TEMPLATE A — FREQUENCY COUNT
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
    freq.merge(c, 1, Integer::sum);          // or: freq.put(c, freq.getOrDefault(c, 0) + 1)
}
// lowercase-only alphabet? use int[26] — faster, no boxing, no hashing:
int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;

// TEMPLATE B — "HAVE I SEEN THE COMPLEMENT?" (one pass, Two-Sum shape)
Map<Integer, Integer> seen = new HashMap<>();     // value -> index
for (int i = 0; i < nums.length; i++) {
    int need = target - nums[i];
    if (seen.containsKey(need)) return new int[]{seen.get(need), i};
    seen.put(nums[i], i);                    // put AFTER the check — avoids matching itself
}

// TEMPLATE C — PREFIX SUM + MAP (subarrays summing to k)
Map<Integer, Integer> prefixCount = new HashMap<>();
prefixCount.put(0, 1);                       // CRITICAL seed: the empty prefix
int sum = 0, result = 0;
for (int x : nums) {
    sum += x;
    result += prefixCount.getOrDefault(sum - k, 0);   // count subarrays ending here
    prefixCount.merge(sum, 1, Integer::sum);
}

// TEMPLATE D — GROUP BY A CANONICAL KEY (anagrams, patterns)
Map<String, List<String>> groups = new HashMap<>();
for (String w : words) {
    char[] ch = w.toCharArray(); Arrays.sort(ch);
    groups.computeIfAbsent(new String(ch), k -> new ArrayList<>()).add(w);
}

The three seeds people forget

1. prefixCount.put(0, 1) — without it you miss every subarray that starts at index 0.
2. Put after check in Template B, or nums[i] matches itself when target == 2*nums[i].
3. computeIfAbsent returns the list, so you can .add(...) in the same expression.

Java API cheat sheet

Want	Use
increment a count	map.merge(k, 1, Integer::sum)
default when missing	map.getOrDefault(k, 0)
lazily create a bucket	map.computeIfAbsent(k, x -> new ArrayList<>())
set semantics + “was it new?”	set.add(x) returns false if already present
keys in sorted order	TreeMap — O(log n) ops, but gives floorKey/ceilingKey

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• “Find if two elements satisfy a condition” (unsorted input)
• “Group elements by a property” (anagrams, frequency)
• “Count occurrences” or “frequency” mentioned
• “Find duplicates” or “first unique” element
• Need O(1) lookup to avoid nested loops

The Algorithm (Pseudocode)

Pattern A: Complement Lookup (Two Sum style)

map = empty HashMap
for each (index, value) in array:
    complement = target - value
    if complement in map:
        return [map[complement], index]
    map[value] = index

Pattern B: Frequency Count

freqMap = empty HashMap
for each element:
    freqMap[element]++
process freqMap for the answer

The ‘Trick’ to Know

• HashMap load factor: Java’s default is 0.75. When 75% full, it resizes (doubles + rehashes all entries). Pre-sizing with new HashMap<>(expectedSize * 4 / 3 + 1) avoids mid-operation resizing.
• For character frequency with known ASCII range, int[26] or int[128] is faster than HashMap.

---

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Two Sum - LC 1

Brute Force: O(n^2)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{};
    }
}

Optimal: HashMap Complement Lookup - O(n)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];

            if (seen.containsKey(complement)) {
                return new int[]{seen.get(complement), i};
            }

            seen.put(nums[i], i);
        }

        return new int[]{};
    }
}

Java Architecture Insights

• Map.getOrDefault(key, 0): Eliminates null checks when counting frequencies.
• computeIfAbsent(key, k -> new ArrayList<>()): Perfect for grouping problems (Group Anagrams). Creates the list only if key is absent.
• Why HashMap over TreeMap? HashMap gives O(1) average. TreeMap gives O(log n) but maintains sorted order - only use it when you need sorted keys.

---

3. Mental Model & Visualization

ASCII Diagram (Two Sum: nums=[2,7,11,15], target=9)

Step 1: num=2, complement=7, map={}        → not found, store {2:0}
Step 2: num=7, complement=2, map={2:0}     → FOUND! return [0, 1]

Senior Mental Trigger

“Need O(1) lookup to avoid nested loop = HashMap.”

---

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty
LC 1	Two Sum	Easy
LC 242	Valid Anagram	Easy
LC 217	Contains Duplicate	Easy
LC 383	Ransom Note	Easy
LC 560	Subarray Sum Equals K	Medium

FAANG ‘Aha!’ Level (Hard/Unintuitive)

#	Problem	Difficulty
LC 49	Group Anagrams	Medium
LC 128	Longest Consecutive Sequence	Medium
LC 347	Top K Frequent Elements	Medium
LC 438	Find All Anagrams	Medium
LC 76	Minimum Window Substring	Hard

---

5. Time & Space Complexity Table

Approach	Time	Space	Notes
Brute Force	O(n^2)	O(1)	Nested loop for all pairs
HashMap	O(n)	O(n)	Single pass with complement lookup
Sorting + Two Ptr	O(n log n)	O(1)	Loses original indices