PPractick

The problem

A music app wants the k most-played songs from a play log (song IDs, with repeats). Counting plays is a hash map. Choosing the top k by count is where a heap helps: keep a min-heap of size k ordered by count, so the weakest of the current top k sits on top and is evicted whenever a more frequent song appears. That's O(n log k), and a bucket sort by frequency does it in O(n). In this version ties are broken toward the smaller ID, and the answer is listed from most to least frequent.

Example: [1, 1, 1, 2, 2, 3], k = 2 → [1, 2].

Function signature

vector<int> topKFrequent(const vector<int>& nums, int k);  // most frequent first; ties: smaller value first

Test cases

Input (nums, k)	Output	Explanation
([1, 1, 1, 2, 2, 3], 2)	[1, 2]	Counts 3, 2, 1
([1], 1)	[1]
([4, 4, 5, 5, 5, 6], 1)	[5]
([1, 2, 2, 3, 3, 3], 3)	[3, 2, 1]
([-1, -1, 7], 1)	[-1]

(Confirm: k is at most the number of distinct values; this version orders the output by frequency, then by value.)

How interviewers phrase it

• "Given an integer array nums and an integer k, return the k most frequent elements" (LeetCode 347), with "better than O(n log n)" as a follow-up.

Clarifying questions to ask

1. Any order for the output? (LeetCode says yes; here it's ordered for determinism.)
2. How should ties at the k-th place be broken?
3. How many distinct values are there compared with n?

Follow-ups to expect

1. "Why a min-heap of size k and not a max-heap of everything?"
2. "How does bucket sort get O(n)?"
3. "Quickselect alternative?"
4. "Streaming version?"
5. "Complexity?"

Related questions

• Task Scheduler Medium
• Hand of Straights Medium
• Design Twitter Medium
• Replace Elements by Their Rank Easy
• Longest subarray with sum K Medium
• Count subarrays with given sum Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in