Frequency Counting with Hash Maps in Java

Frequency counting with hash maps is a fundamental pattern in coding interviews and system design problems, enabling efficient tracking of element occurrences in collections through O(1) average lookup and insertion operations.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What is the expected size range of the input array/string? (e.g., up to 10^6 elements)
2. Are duplicates allowed in the input? How should they be handled?
3. Should I return counts for all elements or just those that meet a specific condition?
4. Can I modify the input structure, or must I work with a copy?
5. What is the target time complexity for follow-ups? (e.g., O(n) or O(n log n))

Restatement of the pattern:
This pattern involves counting occurrences of elements in a collection (array, string, or stream) and using that frequency information to solve problems like finding elements with specific counts, determining uniqueness, or identifying patterns. The solution typically leverages hash maps (or similar frequency-tracking data structures) to achieve efficient lookups and updates.

Signal words and constraint shape:
Key indicators include phrases like "count occurrences," "find elements that appear K times," "determine uniqueness," or "group by frequency." Problems often involve arrays, strings, or streams where elements need to be grouped or filtered based on their frequency.

Assumptions made:

• Input elements are hashable (e.g., integers, strings, or other immutable types).
• The frequency counting is a necessary step in solving the problem.
• The solution can afford to store element frequencies in memory.

Scenario fit:
This pattern is best suited for static or batch scenarios where all input elements are available upfront. It's less appropriate for streaming data where real-time updates to frequencies are required, unless a sliding window or reservoir-based approach is used.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "frequency", "count", "occurrence" of elements
• "most frequent", "least frequent", "top K"
• "duplicate", "unique", "distinct" elements
• "group by", "aggregate by"
• Problems asking to "find elements that appear more than once" or "count occurrences"

Why this pattern fits better than the most common alternatives:

• When we need to track element frequencies, hash maps provide O(1) average lookup and insertion
• Compared to sorting + linear scan (O(n log n)), hash maps give us O(n) time complexity
• Unlike nested loops (O(n²)), hash maps eliminate the need for repeated counting operations
• For problems requiring multiple frequency-based queries, hash maps provide optimal single-pass solution

Conditions where a variation or related pattern applies instead:

• When we only care about relative ordering of frequencies, a priority queue with frequency tracking might be better
• For problems with bounded integer ranges, counting sort or direct indexing may be more efficient
• When we're dealing with streaming data and need to maintain running frequencies, a sliding window approach might be preferred
• For problems where we only care about elements with frequency > 1, a set-based approach might suffice

The core insight that makes this pattern work: The key insight is that we can transform the problem of tracking element occurrences into a simple mapping from elements to their counts, allowing us to answer frequency-based queries in constant time after an initial O(n) pass through the data. This transformation reduces complex counting problems to simple hash table operations.

This pattern is particularly effective when:

1. The problem involves counting or grouping elements
2. We need to process the data in a single pass for efficiency
3. The element space is not too large to make hash table overhead worthwhile
4. We're looking for elements that meet specific frequency criteria

3. Approach Evolution

Interview communication script:

"My first instinct is to solve this with a brute force approach where I check every element against every other element to count frequencies, because that's the most straightforward way to think about it. But that's O(n²) time complexity because for each element I'd have to scan the entire array again. Let me think about how to optimize this...

I notice that if I process elements in a single pass and use a hash map to store element frequencies, I can reduce it to O(n) time. The key insight is that I don't need to reprocess elements multiple times - once I've seen an element, I can just increment its count in the hash map. This way, I'm building up the frequency information in one go rather than repeatedly scanning.

The invariant that must hold is that at any point during processing, the hash map contains accurate counts for all elements that have been processed so far. This allows me to handle the problem in a single pass while maintaining correctness for any frequency-based query."

Brute-force approach and why it is not ideal: The brute force approach would involve nested loops where for each element, we scan the entire array to count occurrences. This results in O(n²) time complexity and is inefficient for large inputs.

Improved approach and the key optimization: The key optimization is using a hash map to store element frequencies during a single pass through the data. This transforms the problem from requiring multiple scans to just one scan, reducing time complexity from O(n²) to O(n).

Final approach with step-by-step reasoning:

1. Initialize an empty hash map to store element frequencies
2. Iterate through the input array once
3. For each element, increment its count in the hash map
4. The hash map now contains all frequency information needed
5. This approach works because we only need to know how many times each element appears, not their relative positions

Important invariants that must hold:

• The hash map always contains accurate frequency counts for elements processed so far
• Each element is only counted once during the single pass
• The frequency count for any element never decreases during processing

4. Data Structure Choice

The primary data structure used is a HashMap<Integer, Integer> to store the frequency count of each element in the input array.

Why HashMap is needed:

• It provides O(1) average time complexity for both insertion and lookup operations
• It naturally handles the key-value relationship where keys are array elements and values are their frequencies
• It dynamically grows to accommodate any number of unique elements in the input

Time and space impact:

• Time complexity: O(n) for building the frequency map where n is the input size
• Space complexity: O(k) where k is the number of unique elements (worst case O(n) when all elements are distinct)

Helper structures:

• No additional helper structures are needed beyond the HashMap for this canonical frequency counting problem
• The solution can be implemented with just the frequency map and basic iteration over input elements

This choice is optimal for the problem since we need to count occurrences of elements and HashMap provides the best balance of time complexity and simplicity for this operation.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works step-by-step.

Example: nums = [4, 5, 6, 7, 8, 9, 10], k = 3

Step 1: Initialize variables

• map = empty HashMap
• result = empty list

Step 2: Process first k elements [4, 5, 6]

• Add 4 to map: map = {4: 1}
• Add 5 to map: map = {4: 1, 5: 1}
• Add 6 to map: map = {4: 1, 5: 1, 6: 1}
• Since window size is now k=3, check for valid subarray
• map.size() = 3, which equals k, so [4,5,6] is valid
• Add to result: result = [[4,5,6]]

Step 3: Slide window by removing leftmost element (4)

• Remove 4 from map: map = {5: 1, 6: 1}
• Add next element (7): map = {5: 1, 6: 1, 7: 1}
• map.size() = 3, which equals k, so [5,6,7] is valid
• Add to result: result = [[4,5,6], [5,6,7]]

Step 4: Continue sliding window

• Remove 5: map = {6: 1, 7: 1}
• Add 8: map = {6: 1, 7: 1, 8: 1}
• map.size() = 3, valid subarray [6,7,8]
• Add to result: result = [[4,5,6], [5,6,7], [6,7,8]]

Step 5: Continue until end of array

• Remove 6: map = {7: 1, 8: 1}
• Add 9: map = {7: 1, 8: 1, 9: 1}
• map.size() = 3, valid subarray [7,8,9]
• Add to result: result = [[4,5,6], [5,6,7], [6,7,8], [7,8,9]]

Step 6: Final window

• Remove 7: map = {8: 1, 9: 1}
• Add 10: map = {8: 1, 9: 1, 10: 1}
• map.size() = 3, valid subarray [8,9,10]
• Add to result: result = [[4,5,6], [5,6,7], [6,7,8], [7,8,9], [8,9,10]]

Edge Case Handling: If the array had fewer than k elements, we'd return empty list immediately. If there were duplicates in a window, they would be handled correctly by the HashMap's frequency counting.

The algorithm terminates because we process each element exactly twice (once when added to window, once when removed), and the loop condition ensures we don't go beyond array bounds.

6. Java Solution

import java.util.*;

public class FrequencyCounter {
    
    /**
     * Returns the most frequent element in the array.
     * If multiple elements have the same max frequency, returns the one that appears first.
     */
    public static int findMostFrequent(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Array cannot be null or empty");
        }
        
        // Map to store frequency of each element
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        
        // Track maximum frequency and the element with that frequency
        int maxFrequency = 0;
        int mostFrequentElement = nums[0];
        
        // Iterate through array to count frequencies
        for (int num : nums) {
            int currentFrequency = frequencyMap.getOrDefault(num, 0) + 1;
            frequencyMap.put(num, currentFrequency);
            
            // Update most frequent element if needed
            if (currentFrequency > maxFrequency) {
                maxFrequency = currentFrequency;
                mostFrequentElement = num;
            }
        }
        
        return mostFrequentElement;
    }
    
    /**
     * Returns all elements that appear with frequency >= k
     */
    public static List<Integer> findElementsWithMinFrequency(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new ArrayList<>();
        }
        
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        
        // Count frequencies
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        // Collect elements with frequency >= k
        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            if (entry.getValue() >= k) {
                result.add(entry.getKey());
            }
        }
        
        return result;
    }
    
    /**
     * Returns the k most frequent elements in the array
     */
    public static List<Integer> topKFrequent(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new ArrayList<>();
        }
        
        // Step 1: Count frequencies
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        // Step 2: Use min-heap of size k to track top k elements
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = 
            new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        
        // Step 3: Process entries to maintain heap size k
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else if (entry.getValue() > minHeap.peek().getValue()) {
                minHeap.poll();
                minHeap.offer(entry);
            }
        }
        
        // Step 4: Extract results
        List<Integer> result = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            result.add(minHeap.poll().getKey());
        }
        
        return result;
    }
}

This solution handles three common frequency counting scenarios:

1. Finding the most frequent element (single result)
2. Finding all elements with frequency ≥ k (multiple results)
3. Finding the k most frequent elements (top-k problem)

The implementation uses HashMap for O(1) average lookup and insertion, and maintains clean separation of concerns with distinct methods for each use case. The top-K approach uses a min-heap to efficiently track the k most frequent elements without sorting all elements.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm makes a single pass through the input array of size n, performing constant-time operations (hash map lookups and updates) for each element. Each hash map operation (put, get, containsKey) has an average time complexity of O(1), resulting in overall linear time complexity.

Space Complexity: O(min(n, k))

Where n is the size of the input array and k is the number of unique elements in the array. In the worst case, when all elements are unique, space complexity is O(n). In the best case (all elements identical), it's O(1). The hash map stores at most k unique elements, where k ≤ n.

Why these bounds are correct:

• The linear time bound is tight because we must examine each element at least once to determine its frequency
• The space bound is optimal for the problem as we must store information about each unique element to compute frequencies
• The hash map's amortized O(1) operations are guaranteed in typical scenarios where the load factor is managed properly

Optimality:

This solution achieves optimal time complexity O(n) since we must read each input element at least once. The space complexity is also optimal for the problem's requirements, as we must store frequency information for unique elements. No better solution exists for this exact problem variant.

The complexity analysis assumes standard hash map implementation with good distribution properties and that the input size is within reasonable bounds for hash map operations to remain O(1) amortized.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty input: Handle gracefully with empty map or zero-length result
• Single element: Ensure single-item collections work correctly
• Null inputs: Validate that null keys/values don't break the solution

Duplicate Values and Repeated States

• Duplicate frequencies: Multiple elements having same frequency should be handled correctly in grouping operations
• Zero frequencies: Elements with zero count must not appear in results when filtering by frequency
• Negative frequencies: If input allows negative counts, ensure proper handling

Boundary Conditions

• Integer overflow: When counting frequencies, large inputs could cause overflow in counters (though unlikely with HashMap)
• Large input sizes: Very large collections may impact performance or memory usage
• Memory constraints: For very large datasets, consider streaming approaches

Common Implementation Mistakes

• Not handling null keys: HashMap allows null keys, but some operations may not handle them gracefully
• Incorrect frequency filtering logic: Misunderstanding whether to include elements with frequency ≥ k or > k
• Modifying input during iteration: Attempting to modify a HashMap while iterating over its entries can throw ConcurrentModificationException
• Using wrong comparison operators: Confusing >= vs > when filtering by frequency thresholds
• Not initializing map entries: Failing to properly initialize counts before incrementing

// Example of proper null key handling:
Map<String, Integer> freqMap = new HashMap<>();
String key = null;
freqMap.put(key, freqMap.getOrDefault(key, 0) + 1);

9. Alternative Approaches

There are several alternative approaches to solving frequency counting problems, each with different trade-offs:

1. Sorting-based approach: Sort the array first and then count consecutive elements. This works in O(n log n) time but requires sorting the input array. It's useful when we want to avoid hash maps entirely or when memory is extremely constrained, but it modifies the input array and has worse time complexity.

2. Frequency array approach: When dealing with integers in a known, limited range (e.g., 0-100), we can use a fixed-size array instead of a HashMap. This reduces space overhead and provides O(1) lookup time, but only works for bounded integer ranges.

3. Two-pass approach with multiple data structures: First pass to build frequency map, second pass to process results. This can be useful when we need to maintain the original order or when processing constraints require multiple passes.

4. Stream-based processing: For streaming data, we might use a sliding window or reservoir sampling approach to maintain frequency counts without storing all elements. This is more complex but necessary for real-time or memory-constrained streaming scenarios.

The chosen hash map approach is optimal for general use cases where we need to count arbitrary elements and don't have constraints on input range or memory usage. It provides O(n) time complexity with clean, readable code that scales well to any input size or element type.

10. Test Cases

import java.util.*;

public class TestCases {
    public static void main(String[] args) {
        // Test Case 1: Basic functionality
        int[] nums1 = {1, 2, 3, 2, 1, 3, 1};
        int k1 = 2;
        // Expected: [1, 2] (both appear 3 times, so top 2 frequent elements)
        System.out.println("Test 1: " + Arrays.toString(topKFrequent(nums1, k1)));
        
        // Test Case 2: Single element array
        int[] nums2 = {5};
        int k2 = 1;
        // Expected: [5]
        System.out.println("Test 2: " + Arrays.toString(topKFrequent(nums2, k2)));
        
        // Test Case 3: All elements same
        int[] nums3 = {1, 1, 1, 1};
        int k3 = 1;
        // Expected: [1]
        System.out.println("Test 3: " + Arrays.toString(topKFrequent(nums3, k3)));
        
        // Test Case 4: Empty array
        int[] nums4 = {};
        int k4 = 0;
        // Expected: []
        System.out.println("Test 4: " + Arrays.toString(topKFrequent(nums4, k4)));
        
        // Test Case 5: With negative numbers
        int[] nums5 = {-1, -1, 2, 2, 3, 3, 3};
        int k5 = 2;
        // Expected: [3, -1] or [3, 2] (3 appears 3 times, -1 and 2 appear 2 times)
        System.out.println("Test 5: " + Arrays.toString(topKFrequent(nums5, k5)));
        
        // Test Case 6: Large frequency difference
        int[] nums6 = {1, 1, 1, 2, 2, 3};
        int k6 = 1;
        // Expected: [1]
        System.out.println("Test 6: " + Arrays.toString(topKFrequent(nums6, k6)));
    }
    
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = 
            new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else if (entry.getValue() > minHeap.peek().getValue()) {
                minHeap.poll();
                minHeap.offer(entry);
            }
        }
        
        int[] result = new int[k];
        int index = 0;
        while (!minHeap.isEmpty()) {
            result[index++] = minHeap.poll().getKey();
        }
        
        return result;
    }
}

Sample test cases:

1. Basic functionality: [1, 2, 3, 2, 1, 3, 1] with k=2 → [1, 2] or [2, 1]
2. Single element: [5] with k=1 → [5]
3. All same elements: [1, 1, 1, 1] with k=1 → [1]
4. Empty input: [] with k=0 → []
5. Negative numbers: [-1, -1, 2, 2, 3, 3, 3] with k=2 → [3, -1] or [3, 2]
6. Large frequency difference: [1, 1, 1, 2, 2, 3] with k=1 → [1]

The test cases cover:

• Normal operation with multiple frequent elements
• Edge case of single element input
• Uniform frequency distribution
• Empty inputs
• Negative numbers and mixed signs
• Clear frequency differences to validate heap behavior

11. Final Summary

The core idea is to leverage hash maps for efficient frequency counting and pattern matching in array problems, enabling O(n) time complexity by trading space for speed. This solution works by maintaining a frequency map to track element occurrences and using sliding window or two-pointer techniques to find optimal subarrays that satisfy frequency-based constraints. The efficiency comes from avoiding nested loops and leveraging hash map's O(1) average lookup time to dynamically adjust windows based on element frequencies, making it optimal for problems where elements need to be counted and their distributions analyzed.