Post

Leetcode 215. Kth Largest Element in an Array

Explanation for Leetcode 215 - Kth Largest Element in an Array, and its solution in Python.

Posted
By Hyeonu(Eric) Kim
1 min read

Problem

Leetcode 215 - Kth Largest Element in an Array

Example:

1
2
3
4
5

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

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

Approach

We can use Heap to pop length of nums - k. Then we will have kth biggest element.

Here is the Python code for the solution:

1
2
3
4
5
6
7
8

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

        for i in range(len(nums)-k):
            heapq.heappop(nums)
        
        return heapq.heappop(nums)

Time Complexity and Space Complexity

Time Complexity: $O(n log (n-k))$ where $n$ is length of nums

Space Complexity: $O(n)$

Leetcode, Heap/Priority Queue, Medium
Leetcode Python Study Heap/Priority Queue Medium
This post is licensed under CC BY 4.0 by the author.