Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Top 'K' Numbers

Problem Statement

Given an unsorted array of numbers, find the ‘K’ largest numbers in it.

Example 1:

Input: [3, 1, 5, 12, 2, 11], K = 3
Output: [5, 12, 11]

Example 2:

Input: [5, 12, 11, -1, 12], K = 3
Output: [12, 11, 12]

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].
  • It is guaranteed that the answer is unique.

Solution

A brute force solution could be to sort the array and return the largest K numbers

.....

.....

.....

Like the course? Get enrolled and start learning!
I

ivanc11235

· 3 years ago

In the solution to this problem, there are images that visually demonstrate the algorithm on an example. But the last 3 images in this sequence are duplicates.

quil

quil

· 3 years ago

I am able to use Priority Queues in C# with no problem on Leetcode but when I try to use it here it is missing an assembly reference.

P

Pete Stenger

· 2 years ago

from heapq import *

class Solution:
  def findKLargestNumbers(self, nums, k):
    # O(n)
    heap = [-n for n in nums]
    heapify(heap)

    # O(k log n)
    return [
      -heappop(heap) for _ in range(k)
    ]
K

k

· 3 years ago

Can't Find different approach as mentioned in Note.

"Note: For a detailed discussion about different approaches to solve this problem, take a look at Kth Smallest Number."

Both ("Top 'K' Numbers" and "Kth Smallest Number") problem solved with same strategy.