Log inSign up
mediumLeetCodeNot Started

Kth Largest Element in an Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on LeetCode
Lesson

Problem Statement

Given an integer array nums and an integer k, return the k-th largest element in the array.

Note that it is the k-th largest element in sorted order, not the k-th distinct element.

Can you solve it in O(N) average time complexity?

Example 1 · Example 1: Basic Array:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Explanation: Sorted order: [6, 5, 4, 3, 2, 1]. The 2nd largest element is 5. Min-Heap (Size 2): (5) / (6)

Example 2 · Example 2: Array with Duplicates:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Explanation: Sorted order: [6, 5, 5, 4, 3, 3, 2, 2, 1]. The 4th largest element is 4.

Constraints:

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why a Min-Heap of size K finds the Kth largest element.
  • Implement Quickselect with randomized pivot selection.
  • Compare average vs worst case complexity of selection algorithms.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find Kth largest or smallest element in an unsorted array.
  • Do not need to sort the remaining elements.
  • Target is single element, not entire sorted list.

Algorithmic Decision Tree:

  • If streaming data, use Min-Heap of size K (O(N log K)).
  • If in-memory array modification is allowed, use Quickselect for O(N) average runtime.

Connected Patterns:

Kth Largest Element in a StreamK Closest Points to OriginTop K Frequent Elements

1. Brute Force — Full Sort

Intuition

Sort the entire array in descending order. Return the element at index k-1.

When to apply: When simplicity is paramount and N is small.

Algorithm

  1. Step 1: Sort nums descending.
  2. Step 2: Return nums[k - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 int findKthLargest(vector<int>& nums, int k) {
9 sort(nums.rbegin(), nums.rend());
10 return nums[k - 1];
11 }
12};
13
14int main() {
15 Solution sol;
16 vector<int> nums = {3, 2, 1, 5, 6, 4};
17 cout << "Kth Largest (Brute Force): " << sol.findKthLargest(nums, 2) << endl;
18 return 0;
19}

Time & Space Complexity

  • Time complexity: O(N log N) — O(N log N) comparison sort.
  • Space complexity: O(1) auxiliary — O(1) in-place auxiliary space.

Why Brute Force Doesn't Scale:

With N = 105, O(N log N) requires ~1.7 * 106 comparisons. Quickselect completes in ~2 * 105 comparisons.

Quickselect executes in ~3ms vs ~25ms for sorting.

2. Better — Min-Heap of Size K

Intuition

Iterate over nums. Push each element into the Min-Heap. If the heap size exceeds K, pop the smallest element. After all elements are processed, the root of the heap is the Kth largest element.

When to apply: Standard approach for streaming data or when K << N.

Algorithm

  1. Step 1: Initialize Min-Heap.
  2. Step 2: For each num in nums: push num to heap.
  3. Step 3: If heap size > k: pop root.
  4. Step 4: Return heap.top().
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6class Solution {
7public:
8 int findKthLargest(vector<int>& nums, int k) {
9 priority_queue<int, vector<int>, greater<int>> minHeap;
10 for (int num : nums) {
11 minHeap.push(num);
12 if ((int)minHeap.size() > k) {
13 minHeap.pop();
14 }
15 }
16 return minHeap.top();
17 }
18};
19
20int main() {
21 Solution sol;
22 vector<int> nums = {3, 2, 1, 5, 6, 4};
23 cout << "Kth Largest (Min-Heap): " << sol.findKthLargest(nums, 2) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(N log K) — O(N log K) bounded by heap size K.
  • Space complexity: O(K) — O(K) auxiliary space for heap.

3. Optimal — Quickselect (Hoare's Selection)

Intuition

The Kth largest element is at index target = N - K in ascending order. Quickselect partitions the array around a random pivot. If pivot index == target, return nums[target]. If pivot < target, recurse on right partition; otherwise recurse on left partition.

When to apply: When maximum performance and O(1) extra space are required in-place.

Algorithm

  1. Step 1: Target index = nums.length - k.
  2. Step 2: Set left = 0, right = nums.length - 1.
  3. Step 3: Partition nums[left ... right] using Lomuto or Hoare partition.
  4. Step 4: If pivot index == target: return nums[target].
  5. Step 5: If pivot index < target: left = pivot + 1; else right = pivot - 1.
  6. Step 6: Repeat until target is found.

Interactive Trace for Kth Largest Element in an Array

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Process first elements up to capacity k=2
Visual state
Values and pointers at this exact step
tree
Root: 2
2
Child: 3
3

Node order shown; add connections to display explicit tree edges.

root: h1
Check / comparison
Next is 1: 1 < root 2 -> discarded.
Decision / next transition
Heap remains [2, 3].
Why this step matters

Step 1: Process first elements up to capacity k=2. Min-Heap has [2, 3]. Root is 2.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cstdlib>
4using namespace std;
5
6class Solution {
7 int partition(vector<int>& nums, int left, int right) {
8 int pivotIndex = left + rand() % (right - left + 1);
9 swap(nums[pivotIndex], nums[right]);
10 int pivot = nums[right];
11
12 int pIndex = left;
13 for (int i = left; i < right; i++) {
14 if (nums[i] <= pivot) {
15 swap(nums[i], nums[pIndex]);
16 pIndex++;
17 }
18 }
19 swap(nums[pIndex], nums[right]);
20 return pIndex;
21 }
22
23public:
24 int findKthLargest(vector<int>& nums, int k) {
25 int target = nums.size() - k;
26 int left = 0, right = nums.size() - 1;
27
28 while (left <= right) {
29 int pIndex = partition(nums, left, right);
30 if (pIndex == target) return nums[target];
31 else if (pIndex < target) left = pIndex + 1;
32 else right = pIndex - 1;
33 }
34 return nums[target];
35 }
36};
37
38int main() {
39 Solution sol;
40 vector<int> nums = {3, 2, 1, 5, 6, 4};
41 cout << "Kth Largest (Quickselect): " << sol.findKthLargest(nums, 2) << endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N) expected, O(N^2) worst case — O(N) expected linear time.
  • Space complexity: O(1) auxiliary — O(1) auxiliary memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Full SortO(N log N)O(1) auxiliarySort array descending and return nums[k - 1].Full O(N log N) sorting.
2.Better — Min-Heap of Size KO(N log K)O(K)Maintain Min-Heap of size K. Discard numbers smaller than root.Heap sift-up and sift-down.
3.Optimal — Quickselect (Hoare's Selection)OptimalO(N) expected, O(N^2) worst caseO(1) auxiliaryPartition array in-place until pivot lands at target index (N - k).Pivot selection.

Common Pitfalls & Crucial Edge Cases

Target index off-by-one

The Kth largest is at index N - k in ascending order.

Deterministic pivot selection

Picking always the last element degrades to O(N2) on sorted arrays; randomize pivot.

Using Max-Heap of size N

Takes O(N) memory and O(N + K log N) time; use Min-Heap of size K.

Crucial Edge Cases to Validate:

  • k == 1 — Returns the maximum element in the array.
  • k == nums.length — Returns the minimum element in the array.
  • Array with all equal elements — Partitioning must handle duplicate pivot values cleanly.
  • Negative numbers — Handled naturally by comparison operations.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly differentiate the Min-Heap (O(N log K) time, O(K) space) and Quickselect (expected O(N) time, O(1) space) approaches.
  2. Mention randomized pivot selection to prevent worst-case O(N2) degradation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does Quickselect achieve expected O(N) runtime while Quicksort takes O(N log N)?

Back to DSA Sheet