DSA-069 · FOCUSED PRACTICE
Kth Largest Element in an Array
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 21330 deterministic checks. Learner drafts are not executed.
Understand the problem
Return the kth largest element of an array, counting repeated values separately. k=1 asks for the maximum; k=n asks for the minimum.
- Non-null int[] with 1–100,000 signed int elements; k is from 1 through nums.length. Invalid k and empty input are outside the contract.
- Return a value, not an index or the kth distinct value. For [5,5,4], the second largest is 5.
- Preserve input. The heap and sorting baseline retain duplicate occurrences. No comparator subtraction is used.
Examples
Input:
nums=[3,2,1,5,6,4], k=2
Output:5Only 6 is strictly greater than 5.
Input:
nums=[5,5,4], k=2
Output:5Duplicate occurrences occupy separate ranks.
Before you start
- PriorityQueue root and insertion/removal costs
- Order statistics with duplicate multiplicity
Recognize the structure
We need a rank, not a fully sorted array. A small heap can retain the top k values seen so far; its smallest retained value is the cutoff. A set would discard required multiplicity.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 102/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
What information can be discarded when only k large occurrences matter?
Hint 2
Make the least valuable retained candidate easy to remove.
Hint 3
Maintain a min-heap of at most k occurrences; return its root.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Sort a copy
Clone and sort the array ascending, then read position n-k. For [3,1,2] and k=2, the sorted copy [1,2,3] yields 2. This is O(n log n) time with O(n) storage for the preserved-input copy. It solves more ordering than the requested one rank requires.
Improve the baseline
Retain only the largest k seen
Insert each value into a min-heap. When its size exceeds k, remove its minimum, the least useful candidate for the retained top k.
Read the cutoff
After processing at least k elements, the heap contains exactly k values. Its root is the smallest among them, which is the kth largest in the processed prefix.
Preserve occurrences
PriorityQueue allows equal values, so repeated occurrences survive as needed. A natural integer ordering avoids overflow-prone custom subtraction.
Why it is correct
Initialize
The empty heap is the top min(k,0) values of the empty prefix.
Preserve
Adding the next value creates the only new candidate. If there are more than k candidates, discarding their minimum leaves exactly the k greatest processed occurrences, including ties. Otherwise all processed values remain.
Finish
Since n≥k, the heap ends with k values and every discarded occurrence is no greater than its cutoff. The root therefore has fewer than k strictly greater values and at least k values greater than or equal to it, establishing the requested rank.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.Arrays;
import java.util.PriorityQueue;
public final class Solution {
public static int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> largest = new PriorityQueue<>();
for (int value : nums) {
largest.offer(value);
if (largest.size() > k) largest.poll();
}
return largest.element();
}
public static int baseline(int[] nums, int k) {
int[] sorted = nums.clone();
Arrays.sort(sorted);
return sorted[sorted.length - k];
}
}
Read the meaningful blocks
Use a min-heap
Its root exposes the weakest retained candidate, not the global maximum.
Trim after insertion
A temporary size k+1 is harmless; after trimming the invariant is restored.
Read element after all input
The contract guarantees a nonempty final heap. Do not deduplicate or poll k times from this retained set.
Complexity
O(n log(k+1)) time and O(k) auxiliary heap storage. Writing log(k+1) also covers k=1, where each update still takes constant work.
Output is one int; the input is preserved. Sorting a copy takes O(n log n) time and O(n) extra storage. Quickselect is a separate mutation/expected-time tradeoff.
Exact-state walkthroughs
Reveal normal and boundary traces
Retain only the top two
Input: {"nums":[3,1,5,2,4],"k":2} · Result: 4
Step 1 of 7: Begin with no retained occurrences.
Sorted display shows heap contents, not Java PriorityQueue internal array order.
Empty at this step.
| Variable | Value |
|---|---|
| k | 2 |
| retainedSorted | [] |
See the affected Java block
1 import java.util.Arrays; 2 import java.util.PriorityQueue; 3 4 public final class Solution { 5 public static int findKthLargest(int[] nums, int k) { 6 PriorityQueue<Integer> largest = new PriorityQueue<>(); 7 for (int value : nums) { 8 largest.offer(value); 9 if (largest.size() > k) largest.poll(); 10 } 11 return largest.element(); 12 } 13 14 public static int baseline(int[] nums, int k) { 15 int[] sorted = nums.clone(); 16 Arrays.sort(sorted); 17 return sorted[sorted.length - k]; 18 } 19 } 20
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with no retained occurrences.
Sorted display shows heap contents, not Java PriorityQueue internal array order.
- k
2- retainedSorted
[]
- Insert one occurrence and trim the smallest if needed.
Retained occurrences are exactly the largest min(k,processedCount) seen.
- value
3- removed
null- retainedSorted
[3]- k
2
- Insert one occurrence and trim the smallest if needed.
Retained occurrences are exactly the largest min(k,processedCount) seen.
- value
1- removed
null- retainedSorted
[1,3]- k
2
- Insert one occurrence and trim the smallest if needed.
Retained occurrences are exactly the largest min(k,processedCount) seen.
- value
5- removed
1- retainedSorted
[3,5]- k
2
- Insert one occurrence and trim the smallest if needed.
Retained occurrences are exactly the largest min(k,processedCount) seen.
- value
2- removed
2- retainedSorted
[3,5]- k
2
- Insert one occurrence and trim the smallest if needed.
Retained occurrences are exactly the largest min(k,processedCount) seen.
- value
4- removed
3- retainedSorted
[4,5]- k
2
- Return the contract result.
The final state satisfies the requested output contract.
- result
4
Duplicates occupy ranks
Input: {"nums":[5,5,4],"k":2} · Result: 5
Step 1 of 5: Begin with no retained occurrences.
Sorted display shows heap contents, not Java PriorityQueue internal array order.
Empty at this step.
| Variable | Value |
|---|---|
| k | 2 |
| retainedSorted | [] |
See the affected Java block
1 import java.util.Arrays; 2 import java.util.PriorityQueue; 3 4 public final class Solution { 5 public static int findKthLargest(int[] nums, int k) { 6 PriorityQueue<Integer> largest = new PriorityQueue<>(); 7 for (int value : nums) { 8 largest.offer(value); 9 if (largest.size() > k) largest.poll(); 10 } 11 return largest.element(); 12 } 13 14 public static int baseline(int[] nums, int k) { 15 int[] sorted = nums.clone(); 16 Arrays.sort(sorted); 17 return sorted[sorted.length - k]; 18 } 19 } 20
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with no retained occurrences.
Sorted display shows heap contents, not Java PriorityQueue internal array order.
- k
2- retainedSorted
[]
- Insert one occurrence and trim the smallest if needed.
Retained occurrences are exactly the largest min(k,processedCount) seen.
- value
5- removed
null- retainedSorted
[5]- k
2
- Insert one occurrence and trim the smallest if needed.
Retained occurrences are exactly the largest min(k,processedCount) seen.
- value
5- removed
null- retainedSorted
[5,5]- k
2
- Insert one occurrence and trim the smallest if needed.
Retained occurrences are exactly the largest min(k,processedCount) seen.
- value
4- removed
4- retainedSorted
[5,5]- k
2
- Return the contract result.
The final state satisfies the requested output contract.
- result
5
Test the contract
Input:
nums=[7], k=1
Output:7Singleton.
Input:
nums=[1,2,3], k=3
Output:1Minimum rank.
Input:
nums=[-3,-1,-2], k=2
Output:-2Negative values.
Input:
nums=[4,4,4], k=2
Output:4All equal.
Common mistakes and counterexamples
Use a set
Counterexample: [5,5,4], k=2 would become 4.
Retain duplicate occurrences.
Keep a size-k max-heap and remove its root
Counterexample: [1,2,3], k=2 would discard large candidates.
Remove the smallest of the retained largest values.
Read ascending index k-1
Counterexample: [1,2,3], k=1 needs 3, not 1.
A sorted ascending baseline reads n-k.
Follow-ups
Maintain kth largest in a stream.
Retain the heap across updates and define behavior until k values exist. Each insertion uses O(log(k+1)) work and O(k) retained state.
Input mutation is allowed and expected linear time is attractive.
Derive quickselect around a partition rank, with duplicate handling, worst-case caveats, and a pivot policy. Do not claim unconditional linear time for randomized selection.
Return the top k distinct values.
Add deduplication deliberately, redefine k validity against distinct count, and coordinate heap/set eviction. This is a changed contract, not a free optimization.