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
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); }}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.