≤ pivot, left of p> pivotpivotoutside [l, r]
private int[] nums;private int k;public int findKthLargest(int[] nums, int k) { this.nums = nums; this.k = nums.length - k; // its index once sorted return quickSelect(0, nums.length - 1);}private int quickSelect(int l, int r) { int pivot = nums[r], p = l; for (int i = l; i < r; i++) { if (nums[i] <= pivot) { int tmp = nums[p]; nums[p] = nums[i]; nums[i] = tmp; p++; } } int tmp = nums[p]; nums[p] = nums[r]; nums[r] = tmp; if (p > k) { return quickSelect(l, p - 1); } else if (p < k) { return quickSelect(p + 1, r); } return nums[p];}
- k (index)
- —
- l, r
- —
- pivot
- —
- p, i
- —
- nums
- —
Why it works
- Brute force sorts and reads
nums[nums.length − k]: O(n log n). A size-k min-heap (as in Kth Largest Element in a Stream) gets O(n log k). - This page shows quickselect, the solution NeetCode walks through for this problem. One partition puts the pivot at its final sorted index
p: everything left of it is ≤ pivot, everything right is > pivot. Ifpis the target index, done; otherwise only one side can hold the answer, so recurse into that side and drop the other. - Cost: on average each partition halves the range, so the work is n + n/2 + n/4 + … ≈ 2n: O(n). It runs in place; the only extra space is the call stack, O(log n) deep on average. Java does not eliminate tail calls either, so the recursion really uses stack; a
whileloop overl,ris what makes it O(1). - Pitfall: always taking the last element as pivot makes sorted input the worst case, O(n²): every partition peels off a single value. Try the "sorted" preset. A random pivot fixes sorted input, but not many equal values: every value ≤ pivot goes left, so the "all equal" preset still peels one value per call whatever the pivot. LeetCode's large tests can make this plain version time out. A three-way partition fixes duplicates; the heap is the safe O(n log k) choice.
- Index, not rank: convert first. The k-th largest sits at index
nums.length − kof the ascending order, so the search comparespwith that index.