215. Kth Largest Element In An Array

215. Kth Largest Element in an Array

Medium

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.

You must solve it in O(n) time complexity.

 

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 <= 105
  • -104 <= nums[i] <= 104




 class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:

        #nums = [x*-1 for x in nums]
#         heapq.heapify(nums)

#         for i in range(len(nums)):
#             num = nums[0]
#             heapq.heappop(nums)

#             if i == k-1:
#                 return -num

        heap = nums[:k]
        heapq.heapify(heap)
        for num in nums[k:]:
            if num > heap[0]:
                heapq.heappushpop(heap, num)

        return heap[0]

Random Note

From python 3.7 dict guarantees that order will be kept as they inserted, and popitem will use LIFO order but we need FIFO type system. so we need OrderedDict which have popIten(last = T/F) for this req. One thing, next(iter(dict)) will return the first key of the dict

Python