Practice Session 4: HashMap Patterns

Problem 1: Top K Frequent Elements

Quick Summary: Find k most frequent elements in array.

Industry Context: Analytics (top products, trending topics), monitoring (frequent errors), log analysis

Solutions

Approach 1: HashMap + Sorting

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }
    
    List<Integer> keys = new ArrayList<>(freq.keySet());
    keys.sort((a, b) -> freq.get(b) - freq.get(a));
    
    return keys.stream().limit(k).mapToInt(i -> i).toArray();
}

Time: O(n log n) - dominated by sorting
Space: O(n)
Tradeoff: Simple but not optimal

Approach 2: HashMap + Min Heap

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }
    
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(
        (a, b) -> freq.get(a) - freq.get(b)
    );
    
    for (int num : freq.keySet()) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = minHeap.poll();
    }
    return result;
}

Time: O(n log k)
Space: O(n + k)
Tradeoff: Better for small k

Approach 3: Bucket Sort (Optimal)

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }
    
    // Bucket[i] contains numbers with frequency i
    List<Integer>[] bucket = new List[nums.length + 1];
    for (int num : freq.keySet()) {
        int frequency = freq.get(num);
        if (bucket[frequency] == null) {
            bucket[frequency] = new ArrayList<>();
        }
        bucket[frequency].add(num);
    }
    
    int[] result = new int[k];
    int idx = 0;
    
    // Iterate from highest frequency
    for (int i = bucket.length - 1; i >= 0 && idx < k; i--) {
        if (bucket[i] != null) {
            for (int num : bucket[i]) {
                result[idx++] = num;
                if (idx == k) break;
            }
        }
    }
    return result;
}

Time: O(n)
Space: O(n)
Tradeoff: Most optimal for general case

Problem 2: Design HashMap

Link: LeetCode 706

Quick Summary: Implement HashMap without using built-in hash table libraries.

Industry Context: Understanding cache implementation, database indexing internals

Solution: Array of Linked Lists (Chaining)

class MyHashMap {
    private static final int SIZE = 10000;
    
    class Node {
        int key, value;
        Node next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private Node[] buckets;
    
    public MyHashMap() {
        buckets = new Node[SIZE];
    }
    
    private int hash(int key) {
        return key % SIZE;
    }
    
    public void put(int key, int value) {
        int idx = hash(key);
        
        if (buckets[idx] == null) {
            buckets[idx] = new Node(key, value);
            return;
        }
        
        Node prev = null, curr = buckets[idx];
        while (curr != null) {
            if (curr.key == key) {
                curr.value = value;
                return;
            }
            prev = curr;
            curr = curr.next;
        }
        prev.next = new Node(key, value);
    }
    
    public int get(int key) {
        int idx = hash(key);
        Node curr = buckets[idx];
        
        while (curr != null) {
            if (curr.key == key) {
                return curr.value;
            }
            curr = curr.next;
        }
        return -1;
    }
    
    public void remove(int key) {
        int idx = hash(key);
        Node curr = buckets[idx];
        
        if (curr == null) return;
        
        if (curr.key == key) {
            buckets[idx] = curr.next;
            return;
        }
        
        while (curr.next != null) {
            if (curr.next.key == key) {
                curr.next = curr.next.next;
                return;
            }
            curr = curr.next;
        }
    }
}

Time: O(1) average, O(n) worst case
Space: O(n + m) where m = table size
Key Concepts: Hash function, collision resolution, load factor

Problem 3: Valid Sudoku

Link: LeetCode 36

Quick Summary: Validate 9x9 Sudoku board (partially filled).

Industry Context: Input validation, constraint checking, state verification

Solutions

Approach 1: Three HashSets

public boolean isValidSudoku(char[][] board) {
    Set<String> seen = new HashSet<>();
    
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char num = board[i][j];
            if (num != '.') {
                if (!seen.add(num + " in row " + i) ||
                    !seen.add(num + " in col " + j) ||
                    !seen.add(num + " in box " + i/3 + "-" + j/3)) {
                    return false;
                }
            }
        }
    }
    return true;
}

Time: O(1) - fixed 9x9 board = 81 cells
Space: O(1) - max 399 = 243 strings
Tradeoff: Clever string encoding, single pass

Approach 2: Separate Arrays (Faster)

public boolean isValidSudoku(char[][] board) {
    boolean[][] rows = new boolean[9][9];
    boolean[][] cols = new boolean[9][9];
    boolean[][] boxes = new boolean[9][9];
    
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                int num = board[i][j] - '1'; // Convert to 0-8
                int boxIdx = (i / 3) * 3 + j / 3;
                
                if (rows[i][num] || cols[j][num] || boxes[boxIdx][num]) {
                    return false;
                }
                
                rows[i][num] = true;
                cols[j][num] = true;
                boxes[boxIdx][num] = true;
            }
        }
    }
    return true;
}

Time: O(1)
Space: O(1) - fixed size arrays
Tradeoff: Faster than HashSet approach, more memory efficient

Problem 4: Insert Delete GetRandom O(1)

Link: LeetCode 380

Quick Summary: Design data structure with O(1) insert, delete, and getRandom.

Industry Context: Load balancer (pick random server), A/B testing (random user selection)

Solution: HashMap + ArrayList

class RandomizedSet {
    private List<Integer> list;
    private Map<Integer, Integer> map; // val -> index in list
    private Random rand;
    
    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
        rand = new Random();
    }
    
    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        
        map.put(val, list.size());
        list.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        
        // Swap with last element
        int idx = map.get(val);
        int lastVal = list.get(list.size() - 1);
        
        list.set(idx, lastVal);
        map.put(lastVal, idx);
        
        // Remove last element
        list.remove(list.size() - 1);
        map.remove(val);
        
        return true;
    }
    
    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

Time: O(1) all operations
Space: O(n)
Key Insight: HashMap for O(1) lookup, ArrayList for O(1) random access
Trick: Swap with last element for O(1) deletion

Problem 5: Copy List with Random Pointer

Link: LeetCode 138

Quick Summary: Deep copy linked list where each node has random pointer to any node.

Industry Context: Object cloning, distributed systems (graph replication), state snapshots

Solutions

Approach 1: HashMap (Two Pass)

class Node {
    int val;
    Node next;
    Node random;
    Node(int val) { this.val = val; }
}
 
public Node copyRandomList(Node head) {
    if (head == null) return null;
    
    Map<Node, Node> map = new HashMap<>();
    
    // First pass: create all nodes
    Node curr = head;
    while (curr != null) {
        map.put(curr, new Node(curr.val));
        curr = curr.next;
    }
    
    // Second pass: link pointers
    curr = head;
    while (curr != null) {
        map.get(curr).next = map.get(curr.next);
        map.get(curr).random = map.get(curr.random);
        curr = curr.next;
    }
    
    return map.get(head);
}

Time: O(n)
Space: O(n) for HashMap
Tradeoff: Clean, straightforward

Approach 2: Interweaving (O(1) Space)

public Node copyRandomList(Node head) {
    if (head == null) return null;
    
    // Step 1: Create copy nodes interleaved
    Node curr = head;
    while (curr != null) {
        Node copy = new Node(curr.val);
        copy.next = curr.next;
        curr.next = copy;
        curr = copy.next;
    }
    
    // Step 2: Assign random pointers
    curr = head;
    while (curr != null) {
        if (curr.random != null) {
            curr.next.random = curr.random.next;
        }
        curr = curr.next.next;
    }
    
    // Step 3: Separate lists
    curr = head;
    Node copyHead = head.next;
    while (curr != null) {
        Node copy = curr.next;
        curr.next = copy.next;
        copy.next = (copy.next != null) ? copy.next.next : null;
        curr = curr.next;
    }
    
    return copyHead;
}

Time: O(n)
Space: O(1) excluding output
Tradeoff: More complex but space-optimal

Java 21+ Features with HashMap

Record Patterns for Cleaner HashMap Operations

// Java 21+
record Pair(int key, int value) {}
 
public void processEntries(List<Pair> pairs) {
    Map<Integer, Integer> map = new HashMap<>();
    
    for (Pair pair : pairs) {
        switch (pair) {
            case Pair(int k, int v) when v > 0 -> map.put(k, v);
            case Pair(int k, int v) when v < 0 -> map.remove(k);
            default -> {} // Skip zeros
        }
    }
}

Enhanced Switch for Frequency Analysis

// Java 21+
public String categorizeFrequency(int count) {
    return switch (count) {
        case int c when c == 1 -> "Unique";
        case int c when c <= 5 -> "Rare";
        case int c when c <= 20 -> "Common";
        default -> "Frequent";
    };
}

Key Takeaways

HashMap Selection Guide

Operation Pattern	Data Structure	Why
Insert/Delete/Search	HashMap	O(1) average
Order matters	LinkedHashMap	Insertion order
Sorted keys needed	TreeMap	O(log n) sorted
Concurrent access	ConcurrentHashMap	Thread-safe
Fixed size, no delete	Array	O(1) guaranteed

Common Patterns

Frequency Counting: map.getOrDefault(key, 0) + 1
Complement Lookup: Store seen elements, check if complement exists
Grouping: Use computed key (sorted string, sum, etc.)
Caching: HashMap + LRU eviction policy
Index Mapping: Value → index for O(1) removal from array

Time Complexity

Average: O(1) for get/put/delete
Worst: O(n) when all keys hash to same bucket
Java’s HashMap uses O(log n) for large buckets (tree-ification)

Space Optimization

Load factor: 0.75 default (resize at 75% capacity)
Initial capacity: Set if size known upfront
Custom hash: Override hashCode() for custom keys

Watch Out For

Mutability: Don’t modify keys after insertion
Null Handling: HashMap allows one null key, null values
Iteration Order: Use LinkedHashMap if order matters
Hash Collisions: Good hash function is critical

Study Notes by Niladri & AI

Explorer

Session-04-HashMap

Practice Session 4: HashMap Patterns

Problem 1: Top K Frequent Elements

Solutions

Approach 1: HashMap + Sorting

Approach 2: HashMap + Min Heap

Approach 3: Bucket Sort (Optimal)

Problem 2: Design HashMap

Solution: Array of Linked Lists (Chaining)

Problem 3: Valid Sudoku

Solutions

Approach 1: Three HashSets

Approach 2: Separate Arrays (Faster)

Problem 4: Insert Delete GetRandom O(1)

Solution: HashMap + ArrayList

Problem 5: Copy List with Random Pointer

Solutions

Approach 1: HashMap (Two Pass)

Approach 2: Interweaving (O(1) Space)

Java 21+ Features with HashMap

Record Patterns for Cleaner HashMap Operations

Enhanced Switch for Frequency Analysis

Key Takeaways

HashMap Selection Guide

Common Patterns

Time Complexity

Space Optimization

Watch Out For

Graph View

Table of Contents

Backlinks