Frequency Map | Engineering Interview Kit

Concept

A Frequency Map (or Frequency Counter) is a highly specific, heavily-tested design pattern that uses a Hash Map to tally the occurrences of elements in a dataset.

Whenever an interview problem asks you to find the “Most Frequent”, “Duplicates”, or “Anagrams”, a Frequency Map is almost always the mathematically optimal solution.

Mental Model

Array: ["apple", "banana", "apple", "cherry", "banana", "apple"]

Look at “apple”. Map is empty. Add "apple": 1.
Look at “banana”. Not in map. Add "banana": 1.
Look at “apple”. It’s in the map! Increment its value. "apple": 2.
…etc.

Final Map:

{
  "apple": 3,
  "banana": 2,
  "cherry": 1
}

Implementation

function buildFrequencyMap(arr: any[]): Map<any, number> {
    const freq = new Map();

    for (let item of arr) {
        // Option 1: The standard IF/ELSE
        if (freq.has(item)) {
            freq.set(item, freq.get(item) + 1);
        } else {
            freq.set(item, 1);
        }

        // Option 2: The elegant One-Liner
        // freq.set(item, (freq.get(item) || 0) + 1);
    }

    return freq;
}

Top K Frequent Elements

Problem: Given an integer array nums and an integer k, return the k most frequent elements. (LeetCode 347).

This problem tests your ability to combine a Frequency Map with a Sorting mechanism.

Approach 1: Frequency Map + Sort ( $O(N \log N)$ )

Build the Frequency Map ( $O(N)$ ).
Convert the Map to an array of pairs: [[value, count], ...].
Sort the array descending based on the count ( $O(N \log N)$ ).
Slice the first K elements.

function topKFrequentSort(nums: number[], k: number): number[] {
    const freq = new Map<number, number>();
    for (let num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }

    // Convert to Array and Sort by frequency
    const sortedArray = Array.from(freq.entries()).sort((a, b) => b[1] - a[1]);

    // Extract the top K keys
    const result: number[] = [];
    for (let i = 0; i < k; i++) {
        result.push(sortedArray[i][0]);
    }
    
    return result;
}

Approach 2: Bucket Sort (The $O(N)$ Optimization)
Interviewers at top companies will ask you to solve this in strict $O(N)$ time without sorting.
You use an array where the Index represents the Frequency, and the Value is an array of numbers that share that frequency.

Because the maximum possible frequency of a number is exactly the length of the original array (e.g., an array of 5 items means a number can appear at most 5 times), we can create a fixed-size Bucket Array.

function topKFrequentBucket(nums: number[], k: number): number[] {
    const freq = new Map<number, number>();
    for (let num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }

    // Create buckets where Index = Frequency
    // Array size is nums.length + 1 (to account for 0 frequency)
    const buckets: number[][] = new Array(nums.length + 1).fill(0).map(() => []);

    for (let [num, count] of freq) {
        buckets[count].push(num); // Place the number in the correct frequency bucket
    }

    const result: number[] = [];
    // Iterate backwards from the highest possible frequency
    for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
        if (buckets[i].length > 0) {
            result.push(...buckets[i]);
        }
    }

    // Edge case if multiple numbers share the same frequency at the K boundary
    return result.slice(0, k); 
}

Interview Questions

Q: A developer uses a standard Javascript {} object as a Frequency Counter. They tally up user inputs: {"alice": 5, "constructor": 1}. When they try to iterate over the keys to find the max, their code crashes unexpectedly. Why?
A: constructor is a reserved prototype property on all Javascript objects. By using user input directly as a key on a plain object, the developer accidentally overwrote the prototype chain (Prototype Pollution). When the algorithm tried to call Object.keys() or loop over it, the corrupted prototype caused the JS engine to throw an error. This is exactly why you must use the Map class for Frequency Counters in production and interviews.

Q: In the “Top K Frequent Elements” problem, instead of Bucket Sort, could you use a Heap?
A: Yes, a Min-Heap of size $K$ is actually the most common standard solution for this problem. You build the Frequency Map in $O(N)$ time. Then, you iterate through the keys, pushing them into a Min-Heap based on their frequency. If the heap size exceeds $K$ , you pop the top (which kicks out the smallest frequency). At the end, the heap contains exactly the $K$ most frequent elements. The time complexity is $O(N \log K)$ , which is slightly slower than Bucket Sort, but scales better if $K$ is extremely small relative to $N$ .