Problem Statement

Given an integer array nums and an integer k, return the $k^{th}$ largest element in the array without sorting the array.

Examples

1. For nums = [3,2,1,5,6,4] $2^{nd}$ largest element is 5
2. For nums = [3,2,3,1,2,4,5,5,6] $4^{th}$ largest element is 4

Solution

Points of Interest

This is clearly a heap problem. We can utilize min-heap of k size to solve this problem.

1. With an empty heap initially, we keep pushing new elements into heap
2. We make sure if heap size grows greater than k, we pop a value from it.
3. Popping values from a min heap means that its smallest value will be removed.
4. In the end we will have a heap with k largest elements from the array, with smallest of that bunch on root. Which is what we want

Algo

1. Create an empty heap array
2. Iterate over nums array
   1. Push current value in heap
   2. If size of heap is greater than k, we pop elements from heap
3. In the end, return the root of the heap, which will be at the 0th index of the heap array

Code

def findKthLargest(nums: List[int], k: int) -> int:
    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

Complexity

$\textbf{Time Complexity} = O(n\log(k))$

• For each element we push element into heap, taking $O(\log(k))$ time
• For most of the elements, we pop element from heap, taking $O(\log(k))$ time

$\textbf{Space Complexity} = O(k)$

• We are maintaining heap array whose size never goes above k