Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Top 'K' Frequent Numbers

Problem Statement

Given an unsorted array of numbers, find the top ‘K’ frequently occurring numbers in it.

Example 1:

Input: [1, 3, 5, 12, 11, 12, 11], K = 2
Output: [12, 11]
Explanation: Both '11' and '12' appeared twice.

Example 2:

Input: [5, 12, 11, 3, 11], K = 2
Output: [11, 5] or [11, 12] or [11, 3]
Explanation: Only '11' appeared twice; all other numbers appeared once.

Constraints:

  • 1 <= nums.length <= 10<sup>5</sup>
  • -10<sup>5</sup> <= nums[i] <= 10<sup>5</sup>
  • k is in the range [1, the number of unique elements in the array].

.....

.....

.....

Like the course? Get enrolled and start learning!
W

Will

· 4 years ago

There's an O(N) time & space solution for this question using a slightly modified version of Bucket Sort, specifically useful for this type of question (top K frequent numbers/ letters- see Bucket Sort filtered questions on Leetcode).

Its usage for optimal solutions isn't common, but it still might be useful to link to/ mention this idea.

Show 1 reply
R

Richard Yuan

· 4 years ago

For the python solution, is there a benefit of the code block of "while minHeap: topNumbers.append(heappop(minHeap)[1])"? Would it not be cheaper time wise to simply iterate through the tuples within minHeap and append the element to topNumbers? This way will result in only O(k) rather than O(klogk) time, which won't matter in the overall time complexity. However, I am just trying to see if there is some advantage to the first approach that I am missing.

Show 1 reply
Abdul Wasay

Abdul Wasay

· 3 years ago

We can use the same loop, where we add/update into map and also checks with the queue top element