Top K Frequent Elements - Flipkart Interview Question & Solution

Top K Frequent Elements

Flipkart

Array

Hash Table

Heap

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Solution Walkthrough

This combines a frequency count with a bounded min-heap, the same "keep only the top k" pattern used in the Kth Largest Element problem.

Build a hash map counting how many times each number appears in nums.
Push [count, number] pairs from the map onto a min-heap ordered by count.
Whenever the heap grows past size k, pop its minimum — this discards the least frequent candidates first, so only the k most frequent numbers can survive.
Once every distinct number has been processed, the heap contains exactly the k most frequent elements. Extract their values.

Counting takes O(n). With d distinct numbers, maintaining a heap bounded at size k costs O(d log k). This beats sorting all distinct counts (O(d log d)) whenever k is small relative to d.

class MinHeap {
    constructor() { this.data = []; }
    size() { return this.data.length; }

    push(pair) { // pair = [count, value]
        this.data.push(pair);
        let i = this.data.length - 1;
        while (i > 0) {
            const parent = Math.floor((i - 1) / 2);
            if (this.data[parent][0] <= this.data[i][0]) break;
            [this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
            i = parent;
        }
    }

    pop() {
        const top = this.data[0];
        const last = this.data.pop();
        if (this.data.length > 0) {
            this.data[0] = last;
            let i = 0;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let smallest = i;
                if (l < this.data.length && this.data[l][0] < this.data[smallest][0]) smallest = l;
                if (r < this.data.length && this.data[r][0] < this.data[smallest][0]) smallest = r;
                if (smallest === i) break;
                [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
                i = smallest;
            }
        }
        return top;
    }
}

function topKFrequent(nums, k) {
    const counts = new Map();
    for (const num of nums) {
        counts.set(num, (counts.get(num) || 0) + 1);
    }

    const heap = new MinHeap();
    for (const [value, count] of counts) {
        heap.push([count, value]);
        if (heap.size() > k) {
            heap.pop(); // discard the least frequent so far
        }
    }

    return heap.data.map(([count, value]) => value);
}

Related Algorithms

Min-Heap →

Hashing →