Frequency Map

Not Started

A frequency map (or hash map) is a fundamental technique used to count occurrences of elements in a collection. It's essential for solving problems involving duplicates, anagrams, and pattern matching. This technique uses a dictionary/map data structure to store elements as keys and their frequencies as values.

Time Complexity: O(n) for building the map, O(1) for lookups

Space Complexity: O(k) where k is the number of unique elements

Use Cases: Finding duplicates, anagrams, most frequent elements, two sum problems

Pattern: Iterate through data once, store frequencies, then query or process

Implementation Examples

# Python - Using dictionary
def count_frequencies(arr):
    """Count frequency of each element"""
    freq_map = {}
    
    for num in arr:
        if num in freq_map:
            freq_map[num] += 1
        else:
            freq_map[num] = 1
    
    return freq_map

# Example usage
arr = [1, 2, 2, 3, 3, 3]
result = count_frequencies(arr)
# Output: {1: 1, 2: 2, 3: 3}

// C++ - Using unordered_map
#include <unordered_map>
#include <vector>

std::unordered_map<int, int> countFrequencies(std::vector<int>& arr) {
    std::unordered_map<int, int> freqMap;
    
    for (int num : arr) {
        freqMap[num]++;
    }
    
    return freqMap;
}

// Example usage
std::vector<int> arr = {1, 2, 2, 3, 3, 3};
auto result = countFrequencies(arr);
// freqMap[1] = 1, freqMap[2] = 2, freqMap[3] = 3

// C# - Using Dictionary
Dictionary<int, int> CountFrequencies(int[] arr) {
    var freqMap = new Dictionary<int, int>();
    
    foreach (int num in arr) {
        if (freqMap.ContainsKey(num)) {
            freqMap[num]++;
        } else {
            freqMap[num] = 1;
        }
    }
    
    return freqMap;
}

// Example usage
int[] arr = { 1, 2, 2, 3, 3, 3 };
var result = CountFrequencies(arr);
// result[1] = 1, result[2] = 2, result[3] = 3

// Java - Using HashMap
HashMap<Integer, Integer> countFrequencies(int[] arr) {
    HashMap<Integer, Integer> freqMap = 
        new HashMap<>();
    
    for (int num : arr) {
        freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
    }
    
    return freqMap;
}

// Example usage
int[] arr = {1, 2, 2, 3, 3, 3};
var result = countFrequencies(arr);
// result.get(1) = 1, result.get(2) = 2, result.get(3) = 3

Common Patterns

Finding Duplicates: Check if any frequency > 1

Most Frequent Element: Find key with max frequency

Anagram Detection: Compare frequency maps of two strings

Two Sum: Store complements in map for O(n) lookup