Kth Largest Element in an Array

Mediumheapquickselectsorting
Category: Heap / Priority Queue
Companies that ask this question:
AmazonFacebookGoogleMicrosoftApple
LeetCode →NeetCode →

Approach

Kth Largest Element in an Array

Problem Statement

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

Note that it is the kth largest element in sorted order, not the kth distinct element.

Can you solve it without sorting?

Examples

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

Intuition

Three Approaches:

  1. Sorting: O(n log n) - simple but not optimal
  2. Min-heap of size k: O(n log k) - good for small k
  3. QuickSelect: O(n) average - optimal but complex

Min-heap approach: Similar to "Kth Largest in Stream"!

  • Keep min-heap of k largest elements
  • Root is kth largest

Pattern Recognition

This is a Top-K Selection problem:

  • Multiple valid approaches
  • Trade-off between simplicity and efficiency
  • Heap approach balances both

Approach

Min-Heap (Recommended)

  1. Build min-heap of first k elements
  2. For remaining elements:
    • If element > heap root:
      • Remove root
      • Add element
  3. Return heap root (kth largest)

Time: O(n log k) - better than sorting when k is small

QuickSelect (Optimal)

Based on quicksort partition:

  • Partition around pivot
  • If pivot index = n-k: found answer
  • Else recurse on appropriate half

Time: O(n) average, O(n²) worst case

Sorting (Simple)

Sort array, return nums[n-k]

Time: O(n log n)

Edge Cases

  • k = 1 (maximum element)
  • k = n (minimum element)
  • Duplicate values
  • Single element
  • All elements same

Complexity Analysis

Min-Heap Approach

  • Time: O(n log k)

    • Build heap: O(k log k)
    • Process n-k elements: O((n-k) log k)
    • Total: O(n log k)

  • Space: O(k)

QuickSelect

  • Time: O(n) average, O(n²) worst
  • Space: O(1) or O(log n) for recursion

Sorting

  • Time: O(n log n)
  • Space: O(1) or O(n)

Best choice depends on:

  • If k is small: Min-heap (O(n log k))
  • If k ≈ n: QuickSelect (O(n) average)
  • If simplicity matters: Sorting

Solution

java
1import java.util.PriorityQueue;
2
3class Solution {
4    public int findKthLargest(int[] nums, int k) {
5        // Min-heap of size k
6        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
7
8        // Add first k elements
9        for (int i = 0; i < k; i++) {
10            minHeap.offer(nums[i]);
11        }
12
13        // Process remaining elements
14        for (int i = k; i < nums.length; i++) {
15            if (nums[i] > minHeap.peek()) {
16                minHeap.poll();
17                minHeap.offer(nums[i]);
18            }
19        }
20
21        // Root is kth largest
22        return minHeap.peek();
23    }
24}
25
Loading visualizer...