LeetCode 215 Kth Largest Element in an Array: Heap vs Quickselect

Kth Largest Element is the standard "selection" problem, and its value in interviews comes from having several correct answers with different trade-offs. An interviewer can learn a lot from which one you pick first, whether you know why the heap is a min-heap, and whether you can explain why quickselect is linear on average but quadratic in the worst case.

This guide covers all four approaches with code in Python, C++ and Java, a partition dry run, the duplicate-heavy test case that breaks textbook quickselect, and a decision table. For a wider look at heap patterns, see the heap and priority queue guide.

The Problem: Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element. It's the kth largest in sorted order, not the kth distinct element. The problem statement asks: can you solve it without sorting?

Constraints: 1 ≤ k ≤ n ≤ 10⁵, values between −10⁴ and 10⁴. So k is always valid, n is large enough that O(n²) is out, and the value range is small, which opens up counting.

A useful reframing: the kth largest is the element that would sit at index n − k if the array were sorted ascending. Quickselect works with that index.

Baseline: Sort and Index

def find_kth_largest_sort(nums, k):
    return sorted(nums)[len(nums) - k]

O(n log n) time. It's correct, short, and a perfectly good first sentence in an interview: "Sorting gives O(n log n). Since we need only one position, not the whole order, we can do better." That sentence motivates both the heap (don't keep everything) and quickselect (don't sort both sides).

Approach 1: Min-Heap of Size k

The idea

Keep the k largest elements seen so far in a min-heap. The root is the smallest of those k, which is exactly the "kth largest so far". For each new number:

• Push it.
• If the heap now has more than k elements, pop the minimum. The popped element can't be among the k largest.

After all numbers, the root is the answer.

Why min-heap, not max-heap

This is the question interviewers ask most about this approach. The heap's job is to evict elements that are too small to be in the top k. The element to evict is the smallest one in the current top k, and a min-heap gives you that in O(log k). A max-heap would put the largest element at the root, which is the one you most want to keep.

import heapq
from typing import List

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for x in nums:
            if len(heap) < k:
                heapq.heappush(heap, x)
            elif x > heap[0]:
                heapq.heapreplace(heap, x)   # pop min and push x in one O(log k) step
        return heap[0]

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> heap;   // min-heap
        for (int x : nums) {
            heap.push(x);
            if ((int)heap.size() > k) heap.pop();
        }
        return heap.top();
    }
};

import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();   // min-heap by default
        for (int x : nums) {
            heap.offer(x);
            if (heap.size() > k) heap.poll();
        }
        return heap.peek();
    }
}

Language notes: C++'s priority_queue is a max-heap by default, so you need greater<int>. Java's PriorityQueue is a min-heap by default. Python's heapq is a min-heap and has no max-heap mode. Getting this backwards is the most common bug in this approach; the C++ STL cheat sheet lists the defaults side by side.

Complexity

Each of the n elements causes at most one push and one pop on a heap of size ≤ k + 1: O(n log k) time, O(k) space. When k is small (top 10 of a million), log k is tiny and this is nearly linear. When k is close to n, flip it: the kth largest is the (n − k + 1)th smallest, so use a max-heap of size n − k + 1.

Alternative: heapify everything, pop k times

Build a max-heap of all n elements in O(n) (bottom-up heapify), then pop k − 1 times and read the root: O(n + k log n) time but O(n) space. In Python, heapq.heapify on negated values does this. It's competitive when k is small, but the size-k heap is usually preferred because it needs O(k) memory and handles streams.

Approach 2: Quickselect

The idea

Quickselect is quicksort that only recurses into one side. Pick a pivot and partition the array so smaller elements are on the left and larger ones on the right. The pivot lands at its final sorted position p.

• If p equals the target index n − k, you're done.
• If the target is left of p, repeat on the left part only.
• Otherwise repeat on the right part only.

Why it's O(n) on average

Partitioning a range of size m costs O(m). With a random pivot, the expected size of the part you keep is a constant fraction of m, so the work forms a shrinking geometric series: roughly n + n/2 + n/4 + … ≤ 2n in a simplified "pivot lands in the middle" model. The precise expected number of comparisons is still a small constant times n, so the expected time is O(n). Quicksort pays O(n log n) because it recurses into both sides; quickselect throws one side away each round.

Why the pivot must be random

If you always pick the first or last element as the pivot, a sorted or reverse-sorted array makes each partition peel off one element: n + (n − 1) + … = O(n²). A uniformly random pivot makes that worst case vanishingly unlikely regardless of input order. Interviewers frequently ask "what's the worst case and how do you avoid it?", so have this answer ready.

Lomuto partition (the textbook version)

import random

def find_kth_largest_lomuto(nums, k):
    target = len(nums) - k                   # index in ascending order
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        r = random.randint(lo, hi)
        nums[r], nums[hi] = nums[hi], nums[r]   # move random pivot to the end
        pivot, store = nums[hi], lo
        for i in range(lo, hi):
            if nums[i] < pivot:
                nums[store], nums[i] = nums[i], nums[store]
                store += 1
        nums[store], nums[hi] = nums[hi], nums[store]   # pivot to its final spot
        if store == target:
            return nums[store]
        if store < target:
            lo = store + 1
        else:
            hi = store - 1

This is correct, and it's the version most tutorials show. But it has a real weakness, covered next.

The Duplicates Problem and the 3-Way Partition

In Lomuto's scheme, everything equal to the pivot goes to the right side. Now imagine an array of 10⁵ copies of the same value. Every partition places the pivot at the far left of the range and keeps nearly everything on the right: each round removes only one element, and the "O(n) average" becomes O(n²), even with random pivots. LeetCode's test set is widely reported to include inputs like this, and plain Lomuto quickselect is known to time out on them.

The fix is the 3-way partition (Dijkstra's Dutch National Flag): split the range into < pivot, == pivot and > pivot. If the target index falls inside the equal block, the answer is the pivot, no matter how many duplicates there are.

import random
from typing import List

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        target = len(nums) - k
        lo, hi = 0, len(nums) - 1
        while True:
            pivot = nums[random.randint(lo, hi)]
            lt, i, gt = lo, lo, hi
            while i <= gt:
                if nums[i] < pivot:
                    nums[lt], nums[i] = nums[i], nums[lt]
                    lt += 1
                    i += 1
                elif nums[i] > pivot:
                    nums[i], nums[gt] = nums[gt], nums[i]
                    gt -= 1                  # don't advance i: the swapped-in value is unchecked
                else:
                    i += 1
            if target < lt:
                hi = lt - 1
            elif target > gt:
                lo = gt + 1
            else:
                return pivot

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        mt19937 rng(random_device{}());
        int target = nums.size() - k;
        int lo = 0, hi = nums.size() - 1;
        while (true) {
            int pivot = nums[uniform_int_distribution<int>(lo, hi)(rng)];
            int lt = lo, i = lo, gt = hi;
            while (i <= gt) {
                if (nums[i] < pivot) swap(nums[lt++], nums[i++]);
                else if (nums[i] > pivot) swap(nums[i], nums[gt--]);
                else ++i;
            }
            if (target < lt) hi = lt - 1;
            else if (target > gt) lo = gt + 1;
            else return pivot;
        }
    }
};

import java.util.concurrent.ThreadLocalRandom;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int target = nums.length - k;
        int lo = 0, hi = nums.length - 1;
        while (true) {
            int pivot = nums[ThreadLocalRandom.current().nextInt(lo, hi + 1)];
            int lt = lo, i = lo, gt = hi;
            while (i <= gt) {
                if (nums[i] < pivot) swap(nums, lt++, i++);
                else if (nums[i] > pivot) swap(nums, i, gt--);
                else i++;
            }
            if (target < lt) hi = lt - 1;
            else if (target > gt) lo = gt + 1;
            else return pivot;
        }
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

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

n = 6, so target index = 6 − 2 = 4 (ascending). To make the run reproducible, suppose the random pivot picks are 4, then 5.

Partition done: [3, 2, 1 | 4 | 6, 5] with lt = gt = 3. Target 4 > gt, so search [4, 5] = [6, 5]. With pivot 5: 6 > 5 swaps to the end, giving [5, 6] with the equal block at index 4. Target 4 is inside it, so the answer is 5. Two partitions touched 6 + 2 elements instead of sorting all of them.

Worst case guarantees: median of medians and nth_element

Random pivots give O(n) expected time, with O(n²) still possible in theory. The median of medians algorithm (group into fives, take medians, recursively find their median as the pivot) guarantees O(n) worst case, but its constant factor makes it slower in practice and it's rarely expected in interviews. Knowing it exists and why it works (the pivot is guaranteed to discard roughly 30% of elements each round) is enough.

In C++, std::nth_element(nums.begin(), nums.begin() + (n - k), nums.end()) does this for you. It's typically implemented as introselect: quickselect that switches to a guaranteed-time fallback if recursion gets too deep. In a real codebase, use it; in an interview, mention it after showing you can write the partition.

Approach 3: Counting Sort When Values Are Bounded

LeetCode bounds values to [−10⁴, 10⁴], only 20,001 possible values. Count each value, then walk from the largest value down, subtracting counts from k until it hits zero.

def find_kth_largest_counting(nums, k):
    lo, hi = min(nums), max(nums)
    counts = [0] * (hi - lo + 1)
    for x in nums:
        counts[x - lo] += 1
    for v in range(len(counts) - 1, -1, -1):  # from largest value down
        k -= counts[v]
        if k <= 0:
            return v + lo

O(n + R) time and O(R) space, where R is the value range. Deterministic, no worst case, and very fast here. The catch is obvious: if values were arbitrary 32-bit integers, R would be about 4 × 10⁹ and this would be useless. Mentioning it shows you read the constraints, and asking "are the values bounded?" before choosing is a good habit. The sorting algorithms comparison covers when counting and radix sorts beat comparison sorts in general.

Heap vs Quickselect vs Counting: Which One to Use

A sensible default in an interview: code the heap first (short, robust, hard to get wrong), state its complexity, then say "if we can modify the array, quickselect gets O(n) on average" and code that if time allows. Most interviewers are happy with that order. Some explicitly want quickselect; if they say "can you do better than n log k?", that's your cue.

Related Problems

The last row connects nicely: when inputs are already sorted, selection becomes a binary search problem rather than a partition problem. See Median of Two Sorted Arrays for that version, and binary search on the answer for the value-space technique behind 378.

How Kth Largest Shows Up in Interviews

This problem is very commonly reported at Amazon, Meta, Microsoft and Google, and in Indian product-company rounds. It's often dressed up as a real scenario: "top k sellers by revenue on Flipkart", "k most active users today", or "the 99th percentile latency from a list of request times". Recognising those as selection problems is part of the test.

A strong answer

1. Clarify: kth largest counting duplicates? Can I modify the array? Is the data a stream? Are values bounded?
2. Baseline: sort, O(n log n).
3. Heap: min-heap of size k with the "why min" explanation. O(n log k), O(k).
4. Quickselect: random pivot, one-sided recursion, O(n) expected. Mention the O(n²) worst case and how randomness and 3-way partitioning protect against it.
5. Constraints-aware extra: counting sort for the bounded range.

Follow-ups to prepare for

• "Data doesn't fit in memory." Stream it through a size-k heap: O(k) memory. For a huge k, use counting by value (if bounded) or a multi-pass approach (find the value range containing the kth element, then refine).
• "Data is spread across 100 machines." Each machine sends its local top k; merge them with a heap. For percentiles at scale, real systems use approximate sketches such as t-digest; mention them only as a pointer.
• "Return the top k, not just the kth." The heap already holds them; quickselect leaves them in the last k positions (unordered).
• "Why is quickselect O(n) on average?" Geometric series of shrinking partitions.
• "Is the heap approach stable/deterministic?" Yes; quickselect's running time is random but its answer is deterministic.

Common mistakes

• Max-heap of size k (keeps the smallest k instead of the largest).
• Forgetting greater<int> in C++.
• Off-by-one on the target index: it's n − k ascending, not k or k − 1.
• Non-random pivot, quadratic on sorted input.
• Lomuto partition on duplicate-heavy input, quadratic again.
• Advancing i after swapping with gt in the 3-way partition, which skips an unexamined element.

If you can explain these four approaches and when each wins, you've also covered the core of most "top K" questions. For more about the complexity reasoning here, especially expected versus worst-case bounds, see time and space complexity explained.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.