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!
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