Back to Main
Learn DSA
Depth-First Search
Greedy Algorithms
Get Premium
Heap
Kth Largest Element in an Array
medium
DESCRIPTION (credit Leetcode.com)
Write a function that takes an array of unsorted integers nums and an integer k, and returns the kth largest element in the array. This function should run in O(n log k) time, where n is the length of the array.
Example 1:
Inputs:
Output:
💻 Desktop Required
The code editor works best on larger screens. Please open this page on your computer to write and run code.
"Write a function that takes an integer array `nums` and an integer `k`, and returns the k-th largest element in the array."
Run your code to see results here
Have suggestions or found something wrong?
Explanation
Approach 1: Sorting
The simplest approach is to sort the array in descending order and return the kth element. This approach has a time complexity of O(n log n) where n is the number of elements in the array, and a space complexity of O(1).
Approach 2: Min Heap
By using a min-heap, we can reduce the time complexity to O(n log k), where n is the number of elements in the array and k is the value of k.
The idea behind this solution is to iterate over the elements in the array while storing the k largest elements we've seen so far in a min-heap. At each element, we check if it is greater than the smallest element (the root) of the heap. If it is, we pop the smallest element from the heap and push the current element into the heap. This way, the heap will always contain the k largest elements we've seen so far.
After iterating over all the elements, the root of the heap will be the kth largest element in the array.
Solution
import heapqdef kth_largest(nums, k):if not nums:returnheap = []for num in nums:if len(heap) < k:heapq.heappush(heap, num)elif num > heap[0]:heapq.heappushpop(heap, num)return heap[0]
kth largest element in an array
0 / 10
1x
Complexity Analysis
Time Complexity: O(n log k). We iterate over all the elements in the array. Comparing the current element with the smallest element in the heap takes O(1) time. In the worst case, we both push and pop each element from the heap, which takes O(log k) time.
Space Complexity: O(k). The space used by the heap to store the k largest elements.
Login to track your progress
Your account is free and you can post anonymously if you choose.