Interview Bootcamp
Vote

0% completed

​

Introduction to Top 'K' Elements Pattern

You are given an array of numbers and a number K. Return the K largest values.

[3, 1, 5, 12, 2, 11]   K = 3   gives 5, 11, 12

Sorting the array and taking the last three works, and costs O(N log N). It also produces something you did not ask for: the exact order of all the other numbers. When K is 3 and N is a million, almost all of that work is wasted.

What you need is a small structure holding the best K values seen so far. It must also report which of those is the weakest. The weakest matters, because a new arrival has to beat it.

.....

.....

.....

Like the course? Get enrolled and start learning!
Miguel

Miguel

· 2 years ago

After going through this section, I feel it might be helpful to put the Pattern: Two Heaps after Patter: Top K Elements . This section is quite heavy with heaps and builds a lot of intuition on when to use minHeaps vs maxHeaps.