Top K Frequent Elements

Bloomberg Interview Question

Problem Overview

Difficulty: Medium
LeetCode Pattern: Heap

Given an integer array nums and an integer k, return the k most frequent elements.

Note: You may return the answer in any order.

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

Output:
· [1,2]

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

Output:
· [2,3]

---

Step 1: Clarify Requirements

• Can k be negative or zero?

  • No.

• Is k always valid?

  • Yes, you can assume k is valid.

• Is the input array sorted?

  • No, it won’t always be sorted.

• What if multiple elements have the same frequency?

  • Any k elements with the highest frequencies are acceptable.

---

Step 2: Discuss Approaches

1/ Sort by Frequency (Suboptimal ⚠️)

• Logic:

  • Count frequency using a hash map

  • Convert map to (val, frequency) list

  • Sort list by frequency

  • Pick top k elements

• Big O:

  • Time Complexity: O(n·logn)

  • Space Complexity: O(n)

---

2/ Use Min-Heap (Optimal ✅)

• Logic:

  • Count frequency using a hash map

  • Use a min-heap of size k

  • Push (frequency, val) into heap

  • If heap size > k:

    • Remove smallest frequency

  • At the end:

    • Heap contains top k elements

    • Return them

• Big O:

  • Time Complexity: O(n·log k)

  • Space Complexity: O(n+k)

---

Step 3: Write Code (Optimal)

Python

---

Java

---

C++

---

Step 4: Answer Follow-Ups

• What if the input has duplicates?

  • Our solution still works.

  • Frequency map handles duplicates.

• What if we want O(n) time?

  • Use bucket sort by frequency.

  • Create array of buckets for frequencies 1..n

  • Place elements into buckets by frequency

  • Iterate buckets from high to low

  • Collect top k elements