Leetcode: Kth largest element

Kth Largest Element in an Array | LeetCode OJ

We need to find the kth largest element in an unsorted array.

There are multiple ways to solve this problem

1. Sort input in descending order, return kth element, O(n*log(n))
2. Selection sort input till kth position, return kth element, O(n*k)
3. Convert input to max heap, pop it k times, O(n+klog(n))
4. Convert input to min heap, pop it n-k+1 times O(n+(n-k)log(n))

An important point to note in this problem is to use heap every time you need to

1. Pick kth smallest/largest element from a list
2. Maintain kth smallest/largest element of a dynamic list

As a corollary to above statements heaps should always be used to maintain min or max value of a dynamic array or streaming numbers

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        heapq.heapify(nums)
        for i in range(len(nums) - k):
            heapq.heappop(nums)
        return heapq.heappop(nums)

Related Questions

1. Given co-ordinates of n points on a 2-d plane find the k closest points to the origin
2. Given a streaming list of integers find the median (Hint: use 2 heaps)