Top K Frequent Elements

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Related Problems
Key Takeaways

📋 Problem Statement

Given an integer array nums and integer k, return the k values with highest frequency. Any output order is acceptable.

Examples

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

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

💡 Key Insights

Frequencies are the primary signal: build a hashmap first.
Max frequency cannot exceed N, enabling bucket indexing.
Bucket scan from high to low yields top-k without sorting all keys.
Heap is good when k is small relative to unique values.

💻 Solution Approaches

Approach 1: Sort by Frequency

Time: O(U log U) | Space: O(U)

Count occurrences, sort keys by frequency descending, take first k. Simple but not optimal under the usual interview constraint.

Approach 2: Min-Heap of Size k

Time: O(U log k) | Space: O(U)

Approach 3: Bucket Frequency Scan (Recommended)

Time: O(N) | Space: O(N)

Python Implementation

          from typing import List


def top_k_frequent(nums: List[int], k: int) -> List[int]:
    counts = {}
    for num in nums:
      counts[num] = counts.get(num, 0) + 1

    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in counts.items():
      buckets[freq].append(num)

    result = []
    for freq in range(len(buckets) - 1, 0, -1):
      for num in buckets[freq]:
        result.append(num)
        if len(result) == k:
          return result

    return result
        

JavaScript Implementation

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

  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, freq] of counts.entries()) {
    buckets[freq].push(num);
  }

  const result = [];
  for (let freq = buckets.length - 1; freq >= 1; freq -= 1) {
    for (const num of buckets[freq]) {
      result.push(num);
      if (result.length === k) {
        return result;
      }
    }
  }

  return result;
}
        

🔍 Step-by-Step Walkthrough

Trace nums=[1,1,1,2,2,3], k=2:

Counts -> {1:3, 2:2, 3:1}
Buckets[3]=[1], Buckets[2]=[2], Buckets[1]=[3]
Scan freq 6..1 -> take 1 (result=[1])
Next freq=2 -> take 2 => [1,2]

⚡ Complexity Analysis

Time: O(N) overall: O(N) counting + O(U) bucket placement + O(N) max bucket scan (bounded by array length).

Space: O(N) worst case when all elements are unique and bucket structure is size N+1.

🔧 Edge Cases

k=1 and all values same.
k == number of unique values.
Negative numbers and mixed sign values.
Ties in frequency (any order accepted).

🧪 Test Cases

Python

def test_top_k_frequent():
    assert set(top_k_frequent([1,1,1,2,2,3], 2)) == {1, 2}
    assert top_k_frequent([1], 1) == [1]
    assert set(top_k_frequent([4,4,4,5,5,6,7,7], 3)) == {4, 5, 7}

    print("all tests passed")

JavaScript

function testTopKFrequent() {
  const r1 = new Set(topKFrequent([1,1,1,2,2,3], 2));
  console.assert(r1.has(1) && r1.has(2), "test 1");

  const r2 = topKFrequent([1], 1);
  console.assert(r2.length === 1 && r2[0] === 1, "test 2");

  const r3 = new Set(topKFrequent([4,4,4,5,5,6,7,7], 3));
  console.assert(r3.has(4) && r3.has(5) && r3.has(7), "test 3");

  console.log("all tests passed");
}

💼 Interview Tips

Start with hashmap counting as the base decomposition.
Call out tradeoff: heap vs bucket depending on k and U.
State that tie order is not constrained by prompt.
Avoid full sort when asked for better than O(N log N).

🔗 Related Problems

Kth Largest Element in an Array
Sort Characters by Frequency
Find Median from Data Stream

🎓 Key Takeaways

Frequency counting is always step one.
Bucket indexing by frequency yields linear-time selection.
Heap strategy is the practical fallback when memory shape matters.