Top ‘K’ Elements

Question 1

215. Kth Largest Element in an Array

Top ‘K’ Numbers
Problem Statement
Given an unsorted array of numbers, find the ‘K’ largest numbers in it.
Input: [3, 1, 5, 12, 2, 11], K = 3

Output: [5, 12, 11]
TC – O(N * logK)
SC – O(K)

Answer 1

SC – O(K)
Pseudo code:
1. Declare min-heap.
2. Insert ‘K’ elements in the min-heap.
3. After the insertion, the heap will have three numbers [3, 1, 5] with ‘1’ being the root as it is the smallest element.
4. We’ll iterate through the remaining numbers and perform the above-mentioned two steps if we find a number larger than the root of the heap.
5. The 4th number is ‘12’ which is larger than the root (which is ‘1’), so let’s take out ‘1’ and insert ‘12’. Now the heap will have [3, 5, 12] with ‘3’ being the root as it is the smallest element.
6. The 5th number is ‘2’ which is not bigger than the root of the heap (‘3’), so we can skip this as we already have top three numbers in the heap.
7. The last number is ‘11’ which is bigger than the root (which is ‘3’), so let’s take out ‘3’ and insert ‘11’. Finally, the heap has the largest three numbers: [5, 12, 11]

Takeaway:
1. User min-heap with K elements which will reduce the time complexity.