Medium·[2026-03-27]
215. Kth Largest Element in an Array
[#heap]
## description
## 215. Kth Largest Element in an Array
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:
plain text
1Input: nums = [3,2,1,5,6,4], k = 2
2Output: 5Example 2:
plain text
1Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
2Output: 4- –1 <= k <= nums.length <= 105
- –-104 <= nums[i] <= 104
Constraints:
## notes
### Intuition
Maintaining a min heap of length k will keep the kth largest elements in it. If the min heap exceeds length k, the smallest of k seen, will be removed, maintaining the kth largest.
### Implementation
Initialize a min heap.
Iterate over the numbers:
- –Add the number to the min heap
- –If the heap exceeds length k, pop from the heap
Return the root of the heap
- –Time: O(n log k), we iterate over the numbers once and the heap operations are worst-case O(log k) because the heap maintains a length of k.
- –Space: O(k), The max size of the heap is O(k).
### Complexity
## solution
python
1from typing import List
2import heapq
3
4class Solution:
5 def findKthLargest(self, nums: List[int], k: int) -> int:
6 heap = []
7 for num in nums:
8 heapq.heappush(heap, num)
9 if len(heap) > k:
10 heapq.heappop(heap)
11 return heap[0]
12
13
14
15if __name__ == "__main__":
16 # Include one-off tests here or debugging logic that can be run by running this file
17 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
18 solution = Solution()
19--EOF--