Definition
- distinct() collapses duplicates so 'Kth largest' means the Kth distinct rank.
- sorted(reverseOrder()) arranges values descending.
- skip(k-1) drops the top k-1 values.
- findFirst() takes the next value as an Optional.
- K=1 gives the maximum; K=2 gives the second-largest.
- Bounded min-heap of size K is O(n log k) for large n with small K.
Priya at the National Bank of India removes duplicate transaction amounts, lines them up from biggest to smallest, counts down K-1 from the top, and picks the next one as the Kth-largest for a tiered reward threshold.
Understanding the Concepts
What does this question ask?
The interviewer wants a generic solution for the Kth largest value. This generalizes the second-largest pattern and tests parameterization and edge case handling.
How do you find the Kth largest element?
package com.bank.service;
import java.util.*;
public class KthLargest {
public static Optional<Integer> findKthLargest(
List<Integer> list, int k) {
if (k < 1) throw new IllegalArgumentException(
"K must be >= 1, got: " + k);
return list.stream()
.distinct()
.sorted(Comparator.reverseOrder())
.skip(k - 1)
.findFirst();
}
public static void main(String[] args) {
List<Integer> amounts = List.of(
50000, 125000, 75000, 125000, 90000, 60000);
for (int k = 1; k <= 6; k++) {
Optional<Integer> result = findKthLargest(amounts, k);
System.out.printf("K=%d: %s%n", k,
result.map(v -> "Rs." + v).orElse("N/A"));
}
}
}
K=1: Rs.125000
K=2: Rs.90000
K=3: Rs.75000
K=4: Rs.60000
K=5: Rs.50000
K=6: N/A
How do you find the Kth smallest?
Replace reverseOrder with natural ascending order.
public static Optional<Integer> findKthSmallest(
List<Integer> list, int k) {
return list.stream()
.distinct()
.sorted(Comparator.naturalOrder())
.skip(k - 1)
.findFirst();
}
What is the efficient approach for large lists?
package com.bank.service;
import java.util.*;
public class KthLargestHeap {
public static Optional<Integer> findKthLargest(
List<Integer> list, int k) {
if (k < 1) throw new IllegalArgumentException("K >= 1");
TreeSet<Integer> topK = new TreeSet<>();
for (int n : list) {
topK.add(n);
if (topK.size() > k) {
topK.pollFirst(); // remove smallest
}
}
return topK.size() == k
? Optional.of(topK.first())
: Optional.empty();
}
}
This bounded set approach is O(n log k), which beats O(n log n) when K is much smaller than n.
How do you handle edge cases?
// K exceeds distinct count: empty
Optional<Integer> beyond = findKthLargest(List.of(100, 200), 5);
System.out.println(beyond.isPresent()); // false
// K = 1: same as max
Optional<Integer> max = findKthLargest(List.of(100, 200), 1);
System.out.println(max.get()); // 200
// Empty list: empty for any K
Optional<Integer> empty = findKthLargest(List.of(), 1);
System.out.println(empty.isPresent()); // false
What are common mistakes?
Mistake: using skip(k) instead of skip(k-1).
// WRONG: skip(3) skips positions 1, 2, 3 and returns position 4
Optional<Integer> wrong = list.stream().distinct()
.sorted(Comparator.reverseOrder())
.skip(3).findFirst(); // 4th largest!
// CORRECT: skip(k-1) for the Kth position
Optional<Integer> correct = list.stream().distinct()
.sorted(Comparator.reverseOrder())
.skip(2).findFirst(); // 3rd largest
Mistake: forgetting distinct when duplicates exist.
// WRONG: if max appears 3 times, K=2 still gives max
Optional<Integer> wrong = List.of(100, 100, 100, 50).stream()
.sorted(Comparator.reverseOrder())
.skip(1).findFirst();
System.out.println(wrong.get()); // 100 (not 50!)
// CORRECT: distinct collapses duplicate values
Optional<Integer> correct = List.of(100, 100, 100, 50).stream()
.distinct()
.sorted(Comparator.reverseOrder())
.skip(1).findFirst();
System.out.println(correct.get()); // 50
What are common interview follow-up questions?
- "How do you find all elements at the Kth rank?" Find the Kth value, then filter the original list for that value.
- "What is the time complexity?" O(n log n) for sort, or O(n log k) for heap.
- "How do you find the Kth largest per department?" Group first, then apply the pattern within each group.
Visual Overview
findKthLargest(list, 3):
List: [50000, 125000, 75000, 125000, 90000, 60000]
│
│ .distinct() → [50000, 125000, 75000, 90000, 60000]
│
│ .sorted(reverseOrder())
▼
[125000, 90000, 75000, 60000, 50000]
│
│ .skip(2) (k-1 = 2)
▼
[75000, 60000, 50000]
│
│ .findFirst()
▼
Optional[75000] ← 3rd-largest
Key Takeaway
The Kth-largest pattern generalizes the second-largest: distinct().sorted(reverseOrder()).skip(k-1).findFirst(). K=1 gives the max, K=2 gives the second-largest, and so on. The distinct step ensures duplicate values count as one rank position, and the Optional honestly handles the case when K exceeds the number of distinct values.
For large lists with small K, the sort-based O(n log n) approach is wasteful. A bounded TreeSet of size K runs in O(n log k) by keeping only the top K values seen so far, with the root being the answer.
At the National Bank of India, Rajesh used this in a rewards program to find the Kth-largest distinct transaction amount as a tiered threshold.
Remember one sentence: distinct-sort(desc)-skip(k-1)-findFirst generalizes to any K, and a bounded heap is faster for small K on large data.
---