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:
Input: nums = [3,2,1,5,6,4], k = 2 Output: 5
Example 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4
Constraints:
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104
This problem asks to find the kth largest element in an array. Several approaches exist, each with different time and space complexity trade-offs. We'll explore three: QuickSelect, using a Priority Queue (Min Heap), and Counting Sort.
Approach: QuickSelect is a variation of the QuickSort algorithm. Instead of sorting the entire array, it recursively partitions the array around a pivot element. The goal is to find the position of the kth largest element without fully sorting.
Algorithm:
Time Complexity: Average case: O(n), Worst case: O(n²). The average case is linear because the partitioning process effectively reduces the problem size by half in each step. The worst-case occurs when the pivot selection consistently leads to highly unbalanced partitions (e.g., always selecting the smallest or largest element).
Space Complexity: O(log n) due to the recursive calls on the call stack. In the worst case, the recursion depth could be O(n).
Code (Python):
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def quickselect(l, r):
if l == r:
return nums[l]
i, j = l - 1, r + 1
pivot = nums[(l + r) // 2]
while i < j:
while True:
i += 1
if nums[i] >= pivot:
break
while True:
j -= 1
if nums[j] <= pivot:
break
if i < j:
nums[i], nums[j] = nums[j], nums[i]
if j < len(nums) - k:
return quickselect(j + 1, r)
return quickselect(l, j)
return quickselect(0, len(nums) - 1)
The code in other languages (Java, C++, Go, TypeScript, Rust) follows a similar approach; the key differences lie in syntax and how they handle array manipulation and recursion.
Approach: A min-heap data structure is used to efficiently track the k largest elements encountered so far.
Algorithm:
k
.k
, add the element to the heap.k
, and the current element is larger than the smallest element in the heap (heap's root), remove the root and insert the current element.Time Complexity: O(n log k). Building the heap takes O(k log k) initially. Then, for each of the remaining n-k
elements, we perform a heap operation (O(log k)).
Space Complexity: O(k) to store the min-heap.
Code (Python):
import heapq
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return heapq.nlargest(k, nums)[-1] # Efficient Python library function
Other language implementations will involve creating a min-heap manually using their respective priority queue libraries.
Approach: Counting sort works well when the input numbers are within a relatively small range. It counts the occurrences of each number.
Algorithm:
Time Complexity: O(n + m), where 'n' is the number of elements, and 'm' is the range of numbers (maximum - minimum). This is linear if 'm' is relatively small compared to 'n'.
Space Complexity: O(m) to store the frequency counts.
Code (Python):
from collections import Counter
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
count = Counter(nums)
for i in range(max(nums), -1, -1):
k -= count[i]
if k <= 0:
return i
This approach is only efficient if the range of numbers is limited; otherwise, it's less efficient than QuickSelect or using a min-heap. The other language versions will have similar structures, using their respective hash map or frequency array implementations.
Choosing the Right Solution:
k
is much smaller than n
. The logarithmic time complexity for heap operations is beneficial in this scenario.