Course4all
Join us on telegram
Home/dsa/Heap / Priority Queue/Kth Largest Element in an Array

Kth Largest Element in an Array

Master this topic with zero to advance depth.

Kth Largest Element in an Array

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 the sorted order, not the kth distinct element.

Visual Representation

nums = [3,2,1,5,6,4], k = 2 Min-Heap (size k=2): [1] -> [1, 2] -> [2, 3] -> [3, 5] -> [5, 6] -> [5, 6] (after 4) Heap top is 5th largest. Quickselect (Partitions): [3, 2, 1, 5, 6, 4] -> pivot 4 [3, 2, 1] | [4] | [5, 6] Target index is in the right partition.
Medium

Examples

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Approach 1

Level I: Sorting (Naive)

Intuition

The simplest way is to sort the entire array in descending order and return the element at index k-1.

Thought Process

  1. Sort the input array.
  2. Access the element at length - k (for ascending sort) or k - 1 (for descending sort).
⏱ O(N log N)💾 O(1) if sorting in place, or O(N)

Detailed Dry Run

nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4

  1. Sorted: [1, 2, 2, 3, 3, 4, 5, 5, 6]
  2. Index (9 - 4) = 5
  3. nums[5] = 4
java
import java.util.Arrays;
class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}
Approach 2

Level II: Quickselect (Average Case Optimal)

Intuition

Based on the Partition logic of Quicksort. We only care about the partition that contains the kkth largest element (index N−kN-k).

Thought Process

  1. Choose a pivot element.
  2. Partition the array around the pivot like in Quicksort.
  3. Compare the pivot's final index with target index N−kN-k.
  4. Recurse into the sub-array containing the target index.
⏱ O(N) Average, O(N^2) Worst Case💾 O(1) excluding recursion stack

Detailed Dry Run

nums = [3, 2, 1, 5, 6, 4], k = 2, target = 6-2 = 4

  1. Partition: [3, 2, 1, 4, 6, 5], 4 is at index 3.
  2. 3 < 4: Recurse [6, 5]
  3. Partition: [5, 6], 6 is at index 5.
  4. 5 > 4: Recurse [5]
  5. Index 4 is 5. Return 5.
java
import java.util.*;
class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
    int quickSelect(int[] nums, int L, int R, int k) {
        int pivot = nums[R], p = L;
        for (int i = L; i < R; i++) {
            if (nums[i] <= pivot) swap(nums, i, p++);
        }
        swap(nums, p, R);
        if (p == k) return nums[p];
        if (p < k) return quickSelect(nums, p + 1, R, k);
        return quickSelect(nums, L, p - 1, k);
    }
    void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
}
Approach 3

Level III: Min-Heap (Optimal)

Intuition

Maintain a Min-Heap of size k. As we iterate through the array, if we find an element larger than the heap's minimum, we replace the minimum with it. After one pass, the heap contains the k largest elements, and the top is the kth largest.

Thought Process

  1. Initialize a Min-Heap.
  2. For each number in nums:
    • Push to heap.
    • If heap size > k, pop the smallest element.
  3. The root of the heap is our answer.
⏱ O(N log K)💾 O(K)

Detailed Dry Run

nums = [3, 2, 1, 5, 6, 4], k = 2

  1. Push 3: Heap [3]
  2. Push 2: Heap [2, 3]
  3. Push 1: Heap [1, 2, 3] -> Pop 1. Heap [2, 3]
  4. Push 5: Heap [2, 3, 5] -> Pop 2. Heap [3, 5]
  5. Push 6: Heap [3, 5, 6] -> Pop 3. Heap [5, 6]
  6. Push 4: Heap [4, 5, 6] -> Pop 4. Heap [5, 6] Result: Top is 5
java
import java.util.PriorityQueue;

public class Main {
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int n : nums) {
            minHeap.add(n);
            if (minHeap.size() > k) minHeap.poll();
        }
        return minHeap.peek();
    }

    public static void main(String[] args) {
        System.out.println(findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2)); // 5
    }
}
← Previous QuestionTop K Frequent Elements
Next Question →Task Scheduler