Hashing Patterns

1. Introduction: Beyond Simple Counting

Basic hashing involves tracking frequencies or looking up direct complements (like in Two Sum). However, interviewers at top companies rarely ask pure frequency questions. Instead, they test your ability to use HashMaps in conjunction with other algorithms to bypass nested loops.

The three most powerful advanced hashing patterns are:

1. Prefix Sum Hashing: Used for solving Subarray problems in $O(N)$ instead of $O(N^2)$.
2. State/Group Hashing: Used for classifying complex data into buckets (like anagrams or overlapping intervals).
3. Rolling Hash (Rabin-Karp): Used for string matching and plagiarism detection in linear time.

2. Core Pattern 1: Prefix Sum + HashMap

Whenever a problem asks you to find a Contiguous Subarray that meets a specific sum condition, and the array contains negative numbers (meaning Sliding Window will fail), you MUST use Prefix Sum Hashing.

Problem Statement: (LeetCode 560) Subarray Sum Equals K. Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

The Math: Let prefix[i] be the sum of all elements from index 0 to i. The sum of a subarray from j to i is exactly prefix[i] - prefix[j-1]. If we want this subarray sum to equal k, then: $prefix[i] - prefix[j-1] = k$ Rearranging the algebra: $prefix[j-1] = prefix[i] - k$

The Insight: As we iterate through the array, we calculate the current prefixSum (prefix[i]). We then check our HashMap to see if we have ever previously seen a prefix sum equal to prefixSum - k. If we have, it mathematically guarantees that the elements between that old prefix and our current index sum exactly to k!

import java.util.HashMap;
import java.util.Map;

public class SubarraySum {
    public static int subarraySum(int[] nums, int k) {
        // Map stores <PrefixSum, Frequency of this PrefixSum>
        Map<Integer, Integer> map = new HashMap<>();
        
        // BASE CASE: A prefix sum of 0 has occurred exactly 1 time (before the array starts)
        // This is CRITICAL. Without it, subarrays that start at index 0 will not be counted.
        map.put(0, 1);
        
        int count = 0;
        int currentPrefixSum = 0;
        
        for (int num : nums) {
            currentPrefixSum += num;
            
            int targetComplement = currentPrefixSum - k;
            
            // Did we see this complement in the past?
            if (map.containsKey(targetComplement)) {
                // Add the NUMBER OF TIMES we saw it to our count
                count += map.get(targetComplement);
            }
            
            // Record our current prefix sum into the map for future iterations
            map.put(currentPrefixSum, map.getOrDefault(currentPrefixSum, 0) + 1);
        }
        
        return count;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. We make one pass.
• Space Complexity: $O(N)$ to store the prefix sums.

3. Core Pattern 2: State/Group Hashing

When you need to group items together based on a shared property, the shared property becomes the HashMap Key, and the Value is a List of the items.

Problem Statement: (LeetCode 49) Group Anagrams. Given an array of strings, group the anagrams together. (e.g., "eat", "tea", "ate" all belong in one group).

The Insight: Two strings are anagrams if and only if their sorted versions are identical. If we sort "eat", we get "aet". If we sort "tea", we get "aet". The sorted string acts as the perfect, unique "Hash Key" for the group!

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class GroupAnagrams {
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for (String s : strs) {
            // 1. Generate the unique Key
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            
            // 2. Initialize the list if the key is new
            map.putIfAbsent(key, new ArrayList<>());
            
            // 3. Add the ORIGINAL string to the group
            map.get(key).add(s);
        }
        
        // 4. Return all the groups
        return new ArrayList<>(map.values());
    }
}

Note: A common interview optimization is replacing the sorting step ($O(K \log K)$) with a 26-character frequency string (1#0#0...) ($O(K)$) to generate the key.

4. Core Pattern 3: The Rolling Hash (Rabin-Karp)

Problem Statement: (LeetCode 28) Implement indexOf. Given two strings needle and haystack, return the index of the first occurrence of needle in haystack.

The brute force compares the needle against every single substring of the haystack taking $O(N \times M)$ time. The Insight: We can use a Sliding Window and calculate the Hash Code of the current window. If the windowHash == needleHash, we found a match! But recalculating the hash of the window from scratch every time takes $O(M)$ time. A Rolling Hash calculates the new hash in $O(1)$ time by mathematically "subtracting" the character that left the window and "adding" the character that entered the window!

Note: This relies on treating the string as a number in a specific base (usually 26 or 256) and using modulo arithmetic to prevent integer overflow.

public class RabinKarp {
    public static int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if (m == 0) return 0;
        if (n < m) return -1;
        
        // Constants for the rolling hash
        int BASE = 256; 
        int MOD = 1000000007; // A large prime number to prevent overflow
        
        long needleHash = 0;
        long windowHash = 0;
        long highestBasePower = 1; // BASE^(m-1)
        
        // Precompute the highest power of BASE for removal
        for (int i = 0; i < m - 1; i++) {
            highestBasePower = (highestBasePower * BASE) % MOD;
        }
        
        // Calculate initial hashes for the needle and the first window
        for (int i = 0; i < m; i++) {
            needleHash = (needleHash * BASE + needle.charAt(i)) % MOD;
            windowHash = (windowHash * BASE + haystack.charAt(i)) % MOD;
        }
        
        // Slide the window
        for (int i = 0; i <= n - m; i++) {
            // Check for match
            if (needleHash == windowHash) {
                // Hash collision check (Double check the actual string)
                if (haystack.substring(i, i + m).equals(needle)) {
                    return i;
                }
            }
            
            // Calculate the rolling hash for the next window
            if (i < n - m) {
                // 1. Remove the leading digit: windowHash - (char * BASE^(m-1))
                windowHash = (windowHash - haystack.charAt(i) * highestBasePower) % MOD;
                if (windowHash < 0) windowHash += MOD; // Handle negative modulo in Java
                
                // 2. Shift base and add the trailing digit
                windowHash = (windowHash * BASE + haystack.charAt(i + m)) % MOD;
            }
        }
        
        return -1;
    }
}

5. Common Mistakes Beginners Make

1. Forgetting map.put(0, 1) in Prefix Sums

   • The Mistake: Initializing the map as empty for Subarray Sum Equals K.
   • Why it's wrong: If the first 3 elements of the array sum exactly to K, currentPrefixSum - k will equal 0. If 0 is not in the map, you will fail to count this perfectly valid subarray. The prefix sum BEFORE the array starts is always mathematically 0.

2. Using .hashCode() instead of actual string comparison in Rabin-Karp

   • The Mistake: Trusting if (windowHash == needleHash) return i;.
   • Why it's wrong: Hashes collide! Two completely different strings can mathematically evaluate to the same modulo hash. You MUST do an actual string comparison .equals() when a hash match is found to verify it is not a collision.

3. Using HashMap for Subarray sums when the array is all positive

   • The Mistake: Using the $O(N)$ Space Prefix Sum Hash pattern when all numbers are strictly $\ge 0$.
   • The Fix: If all numbers are positive, a Sliding Window algorithm solves the problem in $O(N)$ time and $O(1)$ space. Only use the Hash pattern if negative numbers are involved (which break the monotonic property of Sliding Windows).

6. Interview Q&A

Q1: What is a "Sparse Array" or "Sparse Matrix" and how do HashMaps help? Answer: A sparse matrix is one where 99% of the values are 0 (e.g., a massive 100,000 x 100,000 grid representing a map, but only 5 squares have cities). An array would cause an OutOfMemoryError. You can use a Map<String, Integer> where the key is "row,col" to store only the 5 cities, saving gigabytes of memory.

Q2: How do you design a system like bit.ly (URL Shortener)? Answer: This is the ultimate hashing problem. You maintain a central Database (acting as the HashMap). The long URL is Hashed (using MD5 or SHA) and compressed (using Base62 encoding) to generate a short string. You map <ShortString, LongURL>. When a user visits the short link, you do an $O(1)$ lookup and redirect them.

Q3: Can Prefix Sum Hashing be used for 2D Matrices? Answer: Yes! (LeetCode 1074 - Number of Submatrices That Sum to Target). You compress the 2D matrix vertically into a 1D array using a sweep line, and then run the exact 1D Prefix Sum Hash logic on the compressed array.

7. Practice Problems

1. Subarray Sum Equals K (LeetCode 560)
   • Goal: Master the PrefixSum - Target lookup.
2. Contiguous Array (LeetCode 525)
   • Hint: Finding equal number of 0s and 1s. Change all 0s to -1. Now you just need to find the longest subarray that sums to 0 using Prefix Sum Hashing!
3. Repeated DNA Sequences (LeetCode 187)
   • Hint: Master the Rolling Hash (or simple Substring hashing) to find sequences of length 10 that appear more than once.

8. Summary

• Prefix Sum Hashing: The absolute best way to solve subarray summation problems when negative numbers are present. TargetComplement = CurrentSum - K.
• Group Hashing: Generate a unique, normalized string (like a sorted string or a frequency string) to serve as a bucket key for related items.
• Rabin-Karp (Rolling Hash): Slides a window while doing $O(1)$ mathematical updates to the hash, bypassing the $O(M)$ string comparison penalty.