Hash Maps and Sets

# CHAPTER 4

Hash Maps and Sets #

1. Chapter Introduction #

2. What is a Hash Table? #

*How it works (The Magic):*

1. 1. You want to store {"John": 95}.

1. 2. The key "John" is passed through a Hash Function.

1. 3. The Hash Function converts the string "John" into an integer (e.g., 42).

1. 4. The system stores the value 95 at index 42 in a hidden underlying array.

1. 5. Later, when you ask for "John", it runs the hash function, instantly gets 42, and returns 95 in O(1) Time.

3. Hash Sets vs. Hash Maps #

• Hash Map: Stores Key -> Value pairs. Used for mapping relationships or counting frequencies (e.g., {"apple": 5, "banana": 2}).

• Hash Set: Stores ONLY unique Keys (no values). Used purely to check for existence or remove duplicates. (e.g., {"apple", "banana"}). Checking if "apple" in my_set: takes O(1) Time.

4. Hash Collisions (The Interview Question) #

5. Pattern 1: The "Two Sum" Problem #

*Optimized (The Hash Map):* We iterate through the array. For every number, we calculate the difference = target - num. Have we seen this difference before? We use a Hash Map to keep track of numbers we've seen and their indices.

def twoSum(nums, target):
    # Map stores {number: index}
    seen = {} 
    
    for i, num in enumerate(nums):
        diff = target - num
        if diff in seen:
            return [seen[diff], i]
        seen[num] = i
        
    return []
# Time: O(N), Space: O(N)

*Why this is beautiful:* We reduced a quadratic O(N^2) problem down to a linear O(N) problem simply by trading O(N) Space for a Hash Map.

6. Pattern 2: Frequency Maps #

*Example: First Unique Character in a String*

public int firstUniqChar(String s) {
    HashMap<Character, Integer> count = new HashMap<>();
    
    // Build frequency map
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        count.put(c, count.getOrDefault(c, 0) + 1);
    }
    
    // Find the first character with frequency 1
    for (int i = 0; i < s.length(); i++) {
        if (count.get(s.charAt(i)) == 1) return i;
    }
    return -1;
}
// Time: O(N), Space: O(1) (since max 26 English letters)

7. Pattern 3: Finding Duplicates / Intersection #

// Remove duplicates from an array
let arr = [1, 2, 2, 3, 4, 4];
let uniqueSet = new Set(arr); // Set contains {1, 2, 3, 4}
let uniqueArr = Array.from(uniqueSet);

8. Mini Project: Group Anagrams #

1. 1. Create a Hash Map: Map<String, List<String>>.

1. 2. For each string, sort its characters to create a "key" ("aet").

1. 3. Append the original string to the list located at that key in the map.

1. 4. Return the values of the map.

9. Common Mistakes #

• Using Unhashable Types as Keys: In Python, you cannot use a list or a dictionary as a key in a dictionary because they are mutable (can change). You must use an immutable type like a String, Integer, or Tuple.

• Forgetting Space Complexity: When you declare map = {}, you are using extra memory. You must state: "This takes O(N) extra space."

10. Best Practices #

• getOrDefault / .get(key, default): Always use these built-in methods when building frequency maps to elegantly handle keys that do not exist in the map yet, avoiding NullPointerException or KeyError.

11. Exercises #

1. 1. Trace the twoSum algorithm on paper for nums = [3, 2, 4], target = 6.

1. 2. Explain how converting an Array to a Set affects Time and Space complexity.

12. MCQs #

14. Interview Questions #

• Q: "Design a Data Structure that supports insert, delete, and getRandomElement all in O(1) average time complexity." (LeetCode 380. Hint: You need to combine a Hash Map AND an Array).

15. FAQs #

• Q: In an interview, should I explain how the Hash Function works internally?

16. Summary #

17. Next Chapter Recommendation #