Kth Largest Element in an Array
MedPrompt
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: 5Example 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
Approaches
3 approaches with complexity analysis and trade-offs.
Sort the array in descending order and return the kth element.
Algorithm
- Sort the array using Arrays.sort()
- Return the element at index nums.length - k
Walkthrough
This is the most straightforward approach where we sort the array in descending order and return the element at index k-1. While simple to implement, it's not the most efficient solution as it requires sorting the entire array.
public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k];}In this approach, we first sort the array using Java's built-in sorting algorithm (which uses a modified quicksort). After sorting, we return the element at index nums.length - k since the array is sorted in ascending order and we want the kth largest element.
Complexity
Time
O(n log n) where n is the length of the array due to sorting
Space
O(1) as sorting is done in-place in Java's implementation
Trade-offs
Pros
Simple to implement
Easy to understand
Uses built-in sorting function
Cons
Not optimal time complexity
Modifies the original array
Sorts the entire array when we only need the kth largest element
Maintain a min heap of size k to find the kth largest element.
Algorithm
- Create a min heap (PriorityQueue)
- Iterate through the array
- Add each element to the heap
- If heap size exceeds k, remove the smallest element
- Return the top element of the heap
Walkthrough
We can use a min heap to keep track of the k largest elements. We maintain a heap of size k, and for each element in the array, we add it to the heap if the heap size is less than k or if the element is larger than the smallest element in the heap.
public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int num : nums) { minHeap.offer(num); if (minHeap.size() > k) { minHeap.poll(); } } return minHeap.peek();}In this approach, we use a PriorityQueue (which is implemented as a min heap in Java). We keep adding elements to the heap, and whenever the size exceeds k, we remove the smallest element. This way, after processing all elements, the heap contains the k largest elements with the kth largest at the top.
Complexity
Time
O(n log k) where n is the length of the array and k is the given value
Space
O(k) to store the heap
Trade-offs
Pros
More efficient than sorting for large arrays
Doesn't modify the original array
Works well when k is small compared to n
Cons
Uses extra space
Not optimal when k is close to n
Requires a heap data structure
Use the QuickSelect algorithm (based on QuickSort partition) to find the kth largest element.
Algorithm
- Use QuickSelect algorithm with partition scheme
- Choose a pivot element
- Partition array around pivot
- If pivot index is target index, return element
- Otherwise, recurse on appropriate half
- Repeat until kth largest is found
Walkthrough
The QuickSelect algorithm is an optimized approach that uses the partition scheme of QuickSort. Instead of recursing on both sides like in QuickSort, we only recurse on the side that contains the kth largest element.
public int findKthLargest(int[] nums, int k) { return quickSelect(nums, 0, nums.length - 1, nums.length - k);} private int quickSelect(int[] nums, int left, int right, int k) { if (left == right) return nums[left]; int pivotIndex = partition(nums, left, right); if (pivotIndex == k) return nums[k]; else if (pivotIndex < k) return quickSelect(nums, pivotIndex + 1, right, k); else return quickSelect(nums, left, pivotIndex - 1, k);} private int partition(int[] nums, int left, int right) { int pivot = nums[right]; int i = left; for (int j = left; j < right; j++) { if (nums[j] <= pivot) { swap(nums, i, j); i++; } } swap(nums, i, right); return i;} private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;}This approach uses the partition scheme to place elements smaller than the pivot on the left and larger elements on the right. We only need to recurse on the side that contains our target index.
Complexity
Time
Average case O(n), Worst case O(n²) where n is the length of the array
Space
O(1) as it's done in-place
Trade-offs
Pros
Optimal average-case time complexity
No extra space needed
Doesn't need to sort the entire array
Best solution when we only need to find one element
Cons
Modifies the original array
Worst case time complexity is O(n²)
Not stable (doesn't preserve relative order of equal elements)
Solutions
Solution
class Solution {public int findKthLargest(int[] nums, int k) { int n = nums.length; return quickSort(nums, 0, n - 1, n - k); }private int quickSort(int[] nums, int left, int right, int k) { if (left == right) { return nums[left]; } int i = left - 1, j = right + 1; int x = nums[(left + right) >>> 1]; while (i < j) { while (nums[++i] < x) ; while (nums[--j] > x) ; if (i < j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } } if (j < k) { return quickSort(nums, j + 1, right, k); } return quickSort(nums, left, j, k); }}class Solution {public: int findKthLargest(vector<int> &nums, int k) { int n = nums.size(); return quickSort(nums, 0, n - 1, n - k); } int quickSort(vector<int> &nums, int left, int right, int k) { if (left == right) return nums[left]; int i = left - 1, j = right + 1; int x = nums[left + right >> 1]; while (i < j) { while (nums[++i] < x) ; while (nums[--j] > x) ; if (i < j) swap(nums[i], nums[j]); } return j < k ? quickSort(nums, j + 1, right, k) : quickSort(nums, left, j, k); }};class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: lo, hi = 0, len(nums) - 1 while lo <= hi: pos = self . partition(nums, lo, hi) if pos == k - 1: # pos starting from 0, so -1 return nums [ pos ] # partially sorted, desc elif pos > k - 1 : hi = pos - 1 else : # pos < k - 1 lo = pos + 1 return - 1 # or raise exception def partition ( self , nums : List [ int ], lo : int , hi : int ) -> int : pivot , l , r = nums [ lo ], lo + 1 , hi while l <= r : if nums [ l ] < pivot and nums [ r ] > pivot : # larger num at left of pivot, easier to count for k-th lagest nums [ l ], nums [ r ] = nums [ r ], nums [ l ] l += 1 r -= 1 if nums [ l ] >= pivot : l += 1 if nums [ r ] <= pivot : r -= 1 # use nums[l] will lead to infinate looping nums [ lo ], nums [ r ] = nums [ r ], nums [ lo ] # possible there is duplicated num, but will be covered here return r ############## class Solution : def findKthLargest ( self , nums : List [ int ], k : int ) -> int : def quick_sort ( left , right , k ): if left == right : return nums [ left ] i , j = left - 1 , right + 1 x = nums [( left + right ) >> 1 ] while i < j : while 1 : i += 1 if nums [ i ] >= x : break while 1 : j -= 1 if nums [ j ] <= x : break if i < j : nums [ i ], nums [ j ] = nums [ j ], nums [ i ] if j < k : return quick_sort ( j + 1 , right , k ) return quick_sort ( left , j , k ) n = len ( nums ) return quick_sort ( 0 , n - 1 , n - k ) ############ class Solution : def findKthLargest ( self , nums : List [ int ], k : int ) -> int : def quick_sort ( left , right , k ): if left == right : return nums [ left ] i , j = left - 1 , right + 1 x = nums [( left + right ) >> 1 ] while i < j : while 1 : i += 1 if nums [ i ] >= x : break while 1 : j -= 1 if nums [ j ] <= x : break if i < j : nums [ i ], nums [ j ] = nums [ j ], nums [ i ] if j < k : return quick_sort ( j + 1 , right , k ) return quick_sort ( left , j , k ) n = len ( nums ) return quick_sort ( 0 , n - 1 , n - k )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.