Coding interview problems › Heaps & Top-K

🔺 Heaps & Top-K Medium

Kth Largest Element in an Array

Kth Largest Element in an Array: quickselect partitions around a pivot and recurses into one side, O(n) average, plus the heap way. Tested Python, visual.

Also searched as: kth largest element using quickselect · find kth largest without sorting · kth largest using min heap

🎯

Try it live Free

Quickselect & the k-th Largest

Run quickselect in the lab and watch it partition around a pivot, then recurse into only the side holding the answer, discarding the rest each round.

Also useful: Binary Heap & Priority Queue, Quicksort, Partition & Conquer

Open the playground →

The problem

Given an unsorted list of integers and an integer k, return the k-th largest element, counting duplicates (so in [3, 3, 1] the 2nd largest is 3). Try to beat sorting the whole list.

Inputnums = [3, 2, 1, 5, 6, 4], k = 2
Output5
Inputnums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output4

The key insight

The k-th largest is the element that would sit at index n - k if the list were sorted. Quickselect partitions around a pivot, which drops the pivot into its final sorted position, and then recurses into only the side that contains index n - k. Throwing away the other side each round makes it O(n) on average.

Brute force first: Sorting and returning nums[-k] is O(n log n). A min-heap of size k is O(n log k), which is a good alternative answer.

Step-by-step approach

  1. The target index is target = len(nums) - k in ascending sorted order.
  2. Pick a random pivot and partition the range into values below, equal to and above it.
  3. If target falls in the "below" part, continue in that part only.
  4. If it falls in the "above" part, continue there, adjusting the target index.
  5. Otherwise the target is one of the pivot copies: return the pivot.

Python solution

PYTHON 3tested
import random


def find_kth_largest(nums, k):
    target = len(nums) - k              # index in ascending order
    lo, hi = 0, len(nums) - 1
    a = list(nums)                      # do not modify the caller's list
    while True:
        pivot = a[random.randint(lo, hi)]
        # three-way partition of a[lo..hi]: < pivot | == pivot | > pivot
        lt, i, gt = lo, lo, hi
        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]
                lt += 1
                i += 1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]
                gt -= 1
            else:
                i += 1
        if target < lt:
            hi = lt - 1                 # answer is in the smaller part
        elif target > gt:
            lo = gt + 1                 # answer is in the larger part
        else:
            return pivot

Complexity

TimeO(n) average, O(n²) worst
SpaceO(n) for the copy, O(1) in place

With a random pivot, each round keeps on average about half the range, so the work is n + n/2 + n/4 + ... which is about 2n. A consistently bad pivot gives O(n²), which random choice makes extremely unlikely.

Common mistakes

Frequently asked questions

What is the time and space complexity of quickselect?

O(n) on average and O(n²) in the worst case, with a random pivot making the worst case very unlikely. It needs O(1) extra space when done in place; this version copies the input, so it uses O(n).

Should I use a heap or quickselect in an interview?

A min-heap of size k is O(n log k), short to write and works on a stream. Quickselect is faster on average for a fixed array. Mentioning both and their trade-offs is a strong answer.

How does the heap solution work?

Push each number into a min-heap and pop whenever its size exceeds k. The heap then holds the k largest values and its root is the k-th largest. In Python, heapq.nlargest(k, nums)[-1] does the same.

Is there a guaranteed O(n) algorithm?

Yes, median of medians picks a pivot that always discards a constant fraction, giving worst-case O(n). It has large constants and is rarely expected in interviews.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Heaps & Top-K Binary Heap & Priority Queue lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.