Kth Largest Element in an Array

Problem Description

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.

You must solve it without sorting.

Examples

Constraints

• 1 ≤ k ≤ nums.length ≤ 10⁵
• -10⁴ ≤ nums[i] ≤ 10⁴

Two Real Solutions, Two Different Trade-offs

Min-heap of size k: maintain a min-heap. When it exceeds size k, pop the smallest. After all elements, the top is the kth largest. O(n log k) time. Simple, predictable, good for streaming.

QuickSelect: a partial sort that finds the kth element in O(n) average. It’s the technique behind Python’s heapq.nlargest and C++‘s nth_element. The worst case is O(n²), but with random pivot selection it’s essentially O(n) in practice.

Most interviews accept the heap. QuickSelect is the answer if the interviewer asks for O(n) average.

Solution 1: Min-Heap of Size k

import java.util.*;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // evict the smallest; keeps k largest
            }
        }

        return minHeap.peek(); // top of min-heap = kth largest
    }
}

import heapq

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        min_heap = []

        for num in nums:
            heapq.heappush(min_heap, num)
            if len(min_heap) > k:
                heapq.heappop(min_heap)  # evict the smallest

        return min_heap[0]  # top = kth largest

#include <vector>
#include <queue>

class Solution {
public:
    int findKthLargest(std::vector<int>& nums, int k) {
        std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

        for (int num : nums) {
            minHeap.push(num);
            if ((int)minHeap.size() > k) minHeap.pop();
        }

        return minHeap.top();
    }
};

Complexity Analysis:

• Time Complexity: O(n log k). Processing each of n elements costs O(log k) for the heap operations.
• Space Complexity: O(k) for the heap.

Where it breaks: if k = 1, this still processes every element. For finding just the maximum, a single pass is faster. The heap approach shines when k is much smaller than n.

Solution 2: QuickSelect

Partition the array around a pivot (like QuickSort), but only recurse into the partition that contains the kth largest.

import java.util.*;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // kth largest = (n - k)th smallest (0-indexed)
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    private int quickSelect(int[] nums, int left, int right, int targetIndex) {
        int pivot = nums[right];
        int store = left;

        for (int i = left; i < right; i++) {
            if (nums[i] <= pivot) {
                int tmp = nums[i]; nums[i] = nums[store]; nums[store] = tmp;
                store++;
            }
        }
        int tmp = nums[store]; nums[store] = nums[right]; nums[right] = tmp;

        if (store == targetIndex) return nums[store];
        if (store < targetIndex) return quickSelect(nums, store + 1, right, targetIndex);
        return quickSelect(nums, left, store - 1, targetIndex);
    }
}

import random

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        target = len(nums) - k  # kth largest = target-th smallest (0-indexed)

        def quick_select(left: int, right: int) -> int:
            pivot_idx = random.randint(left, right)
            nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
            pivot = nums[right]
            store = left

            for i in range(left, right):
                if nums[i] <= pivot:
                    nums[i], nums[store] = nums[store], nums[i]
                    store += 1

            nums[store], nums[right] = nums[right], nums[store]

            if store == target:
                return nums[store]
            elif store < target:
                return quick_select(store + 1, right)
            else:
                return quick_select(left, store - 1)

        return quick_select(0, len(nums) - 1)

#include <vector>
#include <algorithm>

class Solution {
public:
    int findKthLargest(std::vector<int>& nums, int k) {
        int target = nums.size() - k;
        return quickSelect(nums, 0, nums.size() - 1, target);
    }

private:
    int quickSelect(std::vector<int>& nums, int left, int right, int target) {
        int pivot = nums[right], store = left;
        for (int i = left; i < right; i++) {
            if (nums[i] <= pivot) std::swap(nums[i], nums[store++]);
        }
        std::swap(nums[store], nums[right]);

        if (store == target) return nums[store];
        if (store < target) return quickSelect(nums, store + 1, right, target);
        return quickSelect(nums, left, store - 1, target);
    }
};

Complexity Analysis:

• Time Complexity: O(n) average, O(n²) worst case. Use random pivot selection to make worst case extremely unlikely.
• Space Complexity: O(log n) average recursion stack.

Where it breaks: adversarial inputs (sorted or reverse-sorted arrays) repeatedly select bad pivots, causing O(n²). Randomizing the pivot prevents this in practice. C++‘s std::nth_element uses IntroSelect (a hybrid of QuickSelect and heap sort) to guarantee O(n log n) worst case.

Common Mistakes

• Confusing kth largest with kth smallest index. kth largest = (n-k)th index in sorted ascending order. Off by one here is common.
• Using a max-heap of size n and popping k times. Correct but O(n log n), equivalent to sorting. The min-heap approach is better.
• Not randomizing the pivot in QuickSelect. Deterministic pivot selection on sorted inputs gives O(n²).

Frequently Asked Questions

Why does the min-heap keep the kth largest at the top? The heap always evicts the smallest element when size exceeds k. After processing all elements, the k largest are in the heap, with the smallest of those (the kth largest overall) at the top.

When would you use QuickSelect over a heap in an interview? When the interviewer asks for O(n) time or says “without using a heap.” QuickSelect is also preferred when you can modify the input array in place and want to avoid extra space.

← All Problems