Top K Frequent Elements - Practice Coding Problems

Input & Output

Example 1 — Basic Case

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

› Output: [1,2]

💡 Note: Element 1 appears 3 times, element 2 appears 2 times, element 3 appears 1 time. The 2 most frequent elements are 1 and 2.

Example 2 — Single Element

$ Input: nums = [1], k = 1

› Output: [1]

💡 Note: Only one element exists, so it's the most frequent by default.

Example 3 — Multiple Same Frequency

$ Input: nums = [1,2], k = 2

› Output: [1,2]

💡 Note: Both elements appear once, so both are equally frequent. Return both in any order.

Constraints

1 ≤ nums.length ≤ 10⁵
k is in the range [1, number of unique elements in the array]
-10⁴ ≤ nums[i] ≤ 10⁴
Follow up: Your algorithm's time complexity must be better than O(n log n)

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [1,1,1,2,2,3] and k=2

Count Frequencies

Element 1 appears 3 times, 2 appears 2 times, 3 appears 1 time

Select Top K

Return the 2 most frequent elements: [1,2]

Key Takeaway

🎯 Key Insight: Use bucket sort by frequency to achieve O(n) time complexity and avoid expensive sorting operations

Asked in

G Google 65 a Amazon 58 f Facebook 42 M Microsoft 38 🍎 Apple 25

The key insight is to use frequency counting with bucket sort for optimal O(n) performance. Count element frequencies, then use buckets indexed by frequency to avoid sorting. The bucket sort approach achieves O(n) time and meets the follow-up requirement.

Common Approaches

Approach	Time	Space	Notes
✓ Min Heap Approach	O(n log k)	O(n + k)	Use min heap of size k to track k most frequent elements efficiently
Brute Force with Sorting	O(n log n)	O(n)	Count frequencies, sort all unique elements by frequency, return top k
Bucket Sort (Optimal)	O(n)	O(n)	Group elements by frequency in buckets, then collect from highest frequency buckets

Min Heap Approach — Algorithm Steps

Step 1: Count frequency of each element
Step 2: Use min heap of size k
Step 3: For each element, maintain k largest frequencies
Step 4: Extract all elements from heap

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Build frequency map: {1:3, 2:2, 3:1}

Build Min Heap

Maintain heap of size k with smallest frequencies at root

Extract Results

Pop all elements from heap to get top k frequent

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int freq;
    int num;
} FreqItem;

typedef struct {
    FreqItem* items;
    int size;
    int capacity;
} MinHeap;

MinHeap* createHeap(int capacity) {
    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->items = (FreqItem*)malloc(capacity * sizeof(FreqItem));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void heapifyUp(MinHeap* heap, int index) {
    if (index == 0) return;
    int parent = (index - 1) / 2;
    if (heap->items[parent].freq > heap->items[index].freq) {
        FreqItem temp = heap->items[parent];
        heap->items[parent] = heap->items[index];
        heap->items[index] = temp;
        heapifyUp(heap, parent);
    }
}

void heapifyDown(MinHeap* heap, int index) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int smallest = index;
    
    if (left < heap->size && heap->items[left].freq < heap->items[smallest].freq) {
        smallest = left;
    }
    
    if (right < heap->size && heap->items[right].freq < heap->items[smallest].freq) {
        smallest = right;
    }
    
    if (smallest != index) {
        FreqItem temp = heap->items[index];
        heap->items[index] = heap->items[smallest];
        heap->items[smallest] = temp;
        heapifyDown(heap, smallest);
    }
}

void push(MinHeap* heap, int freq, int num) {
    heap->items[heap->size] = (FreqItem){freq, num};
    heapifyUp(heap, heap->size);
    heap->size++;
}

FreqItem pop(MinHeap* heap) {
    FreqItem min = heap->items[0];
    heap->items[0] = heap->items[heap->size - 1];
    heap->size--;
    heapifyDown(heap, 0);
    return min;
}

int* solution(int* nums, int numsSize, int k, int* returnSize) {
    // Count frequencies
    int freq[20001] = {0};
    int offset = 10000;
    
    for (int i = 0; i < numsSize; i++) {
        freq[nums[i] + offset]++;
    }
    
    // Use min heap of size k
    MinHeap* heap = createHeap(k);
    
    for (int i = 0; i < 20001; i++) {
        if (freq[i] > 0) {
            int num = i - offset;
            if (heap->size < k) {
                push(heap, freq[i], num);
            } else if (freq[i] > heap->items[0].freq) {
                pop(heap);
                push(heap, freq[i], num);
            }
        }
    }
    
    // Extract elements from heap
    int* result = (int*)malloc(k * sizeof(int));
    for (int i = 0; i < k; i++) {
        FreqItem item = pop(heap);
        result[i] = item.num;
    }
    
    *returnSize = k;
    free(heap->items);
    free(heap);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int returnSize;
    int* result = solution(nums, numsSize, k, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log k)

O(n) to count frequencies + O(n log k) to maintain heap of size k

⚡ Linearithmic

Space Complexity

O(n + k)

Hash map uses O(n) space, heap uses O(k) space

⚡ Linearithmic Space

286.3K Views

Very High Frequency

~25 min Avg. Time

8.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Min Heap Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler