Kth Largest Element in an Array

 Problem Statement: Given an integer array nums and an integer k, return the  kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Constraints:

• 1 <= k <= nums.length <= 104
• -104 <= nums[i] <= 104

Source: https://leetcode.com/problems/kth-largest-element-in-an-array/

Leetcode Difficulty: Medium

Asked in: Facebook Amazon ,Apple  Netflix Google

Code:

import heapq

def findKthlargest(self, nums, k):
        """
        nums: List[int]
        k: int
        return: int
        """
        
        heap=[]
        
        for i in nums[:k]:
            heapq.heappush(heap, i)
        
        for i in nums[k:]:
            top = heapq.heappop(heap)
            if i>top:
                heapq.heappush(heap, i)
            else:
                heapq.heappush(heap, top)
        
        
        return heapq.heappop(heap)

Thought Process / Explanation:

The keyword "kth largest" hints me to give a shot to heaps. Heap of size K is enough as we will need to return atmost k elements even if the problem is extended. Min heap suits here because we can replace the top if it's shorter than the new element to be examined.

Thank You!