215. Kth Largest Element in an Array (Python)

Related Topic

Heap.

Description

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Sample I/O

Example 1

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

Example 2

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

Note

You may assume k is always valid, 1 ≤ k ≤ array’s length.

Methodology

The question is very simple and It marked as medium. So Here are two of solutions are acceptable. One is using sort library from python another one is using heap both are O(nlogn) time complexity.

Solution one is using sort and sort the input in descending order and the kth largest elemenet will be the k-1. Python using timesort which time complexity is O(nlogn).

Second solution is general. You can build a heap from input array and pop the heap until there k element left. Building heap is taking O(nlogn) time complexity.

Solution 1:

def findKthLargest(self, nums: List[int], k: int) -> int:
        res = sorted(nums, reverse=True)
        return res[k-1]

BigO

Time complexity : O(nlogn) where n is the size of input

Solution 2:

def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        amount = len(nums)
        while amount > k:
            heapq.heappop(nums)
            amount -= 1
        return nums[0]

BigO

Time complexity : O(nlogn) where n is the size of input