Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Introduction to Top 'K' Elements Pattern

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

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

Sorting the full array works in O(N log N) time.

However, the problem does not need the complete order. It only needs the best K values.

Keep a small group containing the largest values seen so far. When a new value arrives, compare it with the weakest value in that group.

A min heap of size K provides exactly this behaviour. Its smallest value stays at the top.

If a new value is greater than the top, remove the top and add the new value.

.....

.....

.....

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.

Reading Progress

0%

Vote for new content