Skip to content

215. Kth Largest Element In An Array

Array Divide and Conquer Sorting Heap (Priority Queue) Quickselect

Problem - 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.

Can you solve it without sorting?

 

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

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # return nlargest(k, nums)[-1]

        nums = [-num for num in nums]
        result = 0
        heapify(nums)
        while k > 0:
            result = -heappop(nums)
            k -= 1
        return result

Submission Stats:

  • Runtime: 79 ms (64.33%)
  • Memory: 28.7 MB (70.19%)