Learn DSA
Depth-First Search
Greedy Algorithms
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:
Explanation
Approach 1: Sorting
Approach 2: Min Heap
Solution
kth largest element in an array
0 / 10
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n log k) where n
is the number of elements in the array and k
is the input parameter. We iterate over all elements, and in the worst case, we both push and pop each element from the heap, which takes O(log k)
time per element.
Space Complexity: O(k) where k
is the input parameter. The space is 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.