LeetCode · #215

Kth Largest Element in an Array Solution

Given an integer array nums and an integer k, return the kth largest element. Note: it is the kth largest in sorted order, not the kth distinct element.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #215

🏗️

Pattern

Heap — min-heap of size k / Quickselect

Given an integer array nums and an integer k, return the kth largest element in the array. You must solve it in O(n) average time.

Example 1

 Input: nums = [3,2,1,5,6,4], k = 2 Output: 5 // Sorted: [1,2,3,4,5,6] → 2nd largest = 5 

Example 2

 Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4 // Sorted: [1,2,2,3,3,4,5,5,6] → 4th largest = 4 

Constraints

 • 1 ≤ k ≤ nums.length ≤ 10⁵ • -10⁴ ≤ nums[i] ≤ 10⁴  ↑ Must solve in O(n) average — sorting alone is O(n log n) 

Section Two · Approach 1

Sort — O(n log n)

Sort the array in descending order. The answer is at index k - 1. Correct and simple, but doesn't meet the O(n) average requirement.

Why it works

Sorting places all elements in order. The kth largest is directly accessible by index. No element is missed.

Why we can do better

Problem: Sorting does O(n log n) work, but we only need one element — the kth largest. A min-heap of size k finds it in O(n log k), and quickselect does it in O(n) average by partitioning without fully sorting.

Java — Sort

 import java.util.Arrays;
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
    }
}

Python — Sort

 class Solution:
def findKthLargest(self, nums: list[int], k: int) -> int:
        nums.sort()
return nums[-k]

Metric	Value
Time	O(n log n)
Space	O(1) — in-place sort (or O(n) for Python's timsort)

Section Three · Approach 2

Min-Heap of Size k — O(n log k)

Maintain a min-heap of at most k elements. Iterate through the array — if the heap has fewer than k elements, add the current one; otherwise, add it and poll the smallest. After processing all elements, the root is the kth largest.

💡 Mental model: Imagine selecting the top-k scorers from a nationwide exam. You have a leaderboard with k slots. Each new score is compared against the current lowest on the board — if it's higher, it bumps the weakest off. After all scores are checked, the bottom of the leaderboard is your kth-best score.

Algorithm

Step 1: Create an empty min-heap.
Step 2: For each element in nums: offer it to the heap.
Step 3: If heap size exceeds k, poll the root (smallest).
Step 4: After all elements, return heap.peek().

🎯 When to recognize this pattern:

"Find the kth largest/smallest" in a static array — think min-heap of size k for the clean O(n log k) solution, or quickselect for the interview-flashy O(n) average solution.
This appears in LC 215, LC 347 (Top K Frequent), LC 973 (K Closest Points), and LC 703 (Kth Largest in Stream).

Quickselect alternative:

Based on quicksort's partition. Pick a pivot, partition so elements ≥ pivot are on the left.
If pivot lands at index k-1, it's the answer. Otherwise recurse on the side containing the target.
O(n) average, O(n²) worst-case. Randomized pivot avoids worst-case in practice.

Section Four · Trace

Visual Walkthrough

Trace min-heap approach with nums = [3, 2, 1, 5, 6, 4], k = 2:

Min-Heap of size k=2 — root is always the kth largest

Notice:

The heap never grows beyond k=2 elements. After processing all 6 elements, only the top-2 (5 and 6) remain.
The root (5) is the 2nd largest. Total work: 6 offers + 4 polls = O(n log k).

Section Five · Implementation

Code — Java & Python

Java — Min-Heap of size k

 import java.util.PriorityQueue;
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap for (int num : nums) {
            heap.offer(num);
if (heap.size() > k)
                heap.poll(); // evict smallest — keeps top-k
}
return heap.peek(); // root = kth largest
}
}

Python — Min-Heap of size k (or heapq.nlargest)

 import heapq
class Solution:
def findKthLargest(self, nums: list[int], k: int) -> int:
        heap = []
for num in nums:
            heapq.heappush(heap, num)
if len(heap) > k:
                heapq.heappop(heap) # evict smallest return heap[0] # root = kth largest # One-liner alternative: return heapq.nlargest(k, nums)[-1] 

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Sort	O(n log n)	O(1)	Simple; overshoots by sorting everything
Min-Heap size k	O(n log k)	O(k)	Clean, predictable. Best when k ≪ n.
Quickselect ← optimal	O(n) avg	O(1)	O(n²) worst-case; randomize pivot to avoid.

Heap vs Quickselect:

The heap approach is simpler and has a guaranteed O(n log k) bound. Quickselect is O(n) average but O(n²) worst-case.
In interviews, most interviewers accept the heap solution. Mention quickselect as a follow-up to show depth.
For production code, std::nth_element (C++) or randomized quickselect is preferred.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
k = 1 (maximum)	`[3,1,2], k=1`	Heap of size 1 → just track the max. Returns 3.
k = n (minimum)	`[3,1,2], k=3`	Heap holds all elements. Root = minimum = 1.
All duplicates	`[5,5,5], k=2`	Heap holds [5,5]. Peek = 5. Duplicates are counted individually.
Negative numbers	`[-1,-2,-3], k=1`	Largest is -1. Heap handles negatives correctly.
Single element	`[42], k=1`	Only one element → return it.
Already sorted descending	`[5,4,3,2,1], k=3`	First k elements fill heap, rest get polled. Answer: 3.

⚠ Common Mistake: Using a max-heap of size n instead of a min-heap of size k. A max-heap would require polling k times to reach the kth largest — O(k log n) — which is worse than the min-heap approach when k is large. The min-heap of size k trick is the key insight: the root directly gives the kth largest.

← Back to Heap problems

LearningTree

LC 215 · Kth Largest Element in an Array — Solution & Explanation | DSA Guide