215. Kth Largest Element in an Array (Medium)

Problem

Given an integer array nums and an integer k, return the k-th largest element in the array. Note: it’s the k-th largest in sorted order, not distinct.

Can you do this without sorting?

Example

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

LeetCode 215 · Link · Medium

Try it yourself

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, sort, index

def find_kth_largest(nums, k):
    nums.sort()       # L1: O(n log n)
    return nums[-k]   # L2: O(1) index

function findKthLargest(nums: number[], k: number): number {
    const arr = [...nums].sort((a, b) => a - b);  // L1: O(n log n)
    return arr[arr.length - k];                    // L2: O(1) index
}

import "sort"

func findKthLargest(nums []int, k int) int {
    arr := make([]int, len(nums))
    copy(arr, nums)
    sort.Ints(arr)        // L1: O(n log n)
    return arr[len(arr)-k] // L2: O(1) index
}

final class Solution {
    func findKthLargest(_ nums: [Int], _ k: Int) -> Int { nums.sorted(by: >)[k - 1] }
}

Where the time goes, line by line

Variables: n = number of elements in nums, k = the rank parameter.

Line	Per-call cost	Times executed	Contribution
L1 (sort)	$O(n log n)$	1	$O(n log n)$ ← dominates
L2 (index)	$O(1)$	1	$O(1)$

Complexity

Time: $O(n log n)$ , driven by L1.
Space: $O(1)$ or $O(log n)$ depending on sort.

Fastest to write; doesn’t meet the “without sorting” challenge.

Approach 2: Size-K min-heap

Maintain a min-heap of size k; the top is the kth largest.

import heapq

def find_kth_largest(nums, k):
    heap = []
    for x in nums:                 # L1: iterate n elements
        heapq.heappush(heap, x)    # L2: O(log k) push
        if len(heap) > k:
            heapq.heappop(heap)    # L3: O(log k) pop to keep size k
    return heap[0]

# Equivalent one-liner:
# return heapq.nlargest(k, nums)[-1]

class MinHeap {
    private data: number[] = [];
    get size(): number { return this.data.length; }
    get top(): number { return this.data[0]; }
    push(val: number): void {
        this.data.push(val);
        this._siftUp(this.data.length - 1);
    }
    pop(): number {
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) { this.data[0] = last; this._siftDown(0); }
        return top;
    }
    private _siftUp(i: number): void {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.data[p] <= this.data[i]) break;
            [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p;
        }
    }
    private _siftDown(i: number): void {
        const n = this.data.length;
        while (true) {
            let smallest = i;
            const l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && this.data[l] < this.data[smallest]) smallest = l;
            if (r < n && this.data[r] < this.data[smallest]) smallest = r;
            if (smallest === i) break;
            [this.data[smallest], this.data[i]] = [this.data[i], this.data[smallest]]; i = smallest;
        }
    }
}

function findKthLargest(nums: number[], k: number): number {
    const heap = new MinHeap();
    for (const x of nums) {       // L1: iterate n elements
        heap.push(x);              // L2: O(log k) push
        if (heap.size > k)
            heap.pop();            // L3: O(log k) pop to keep size k
    }
    return heap.top;
}

package main

import (
    "container/heap"
    "fmt"
)

type MinHeap []int
func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() any {
    old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x
}

func findKthLargest(nums []int, k int) int {
    h := &MinHeap{}
    heap.Init(h)
    for _, x := range nums {  // L1: iterate n elements
        heap.Push(h, x)        // L2: O(log k) push
        if h.Len() > k {
            heap.Pop(h)        // L3: O(log k) pop to keep size k
        }
    }
    return (*h)[0]
}

func assert(condition bool, msgs ...string) {
    if !condition { msg := "assertion failed"; if len(msgs) > 0 { msg = msgs[0] }; panic(msg) }
}

func runTests() {
    assert(findKthLargest([]int{3, 2, 1, 5, 6, 4}, 2) == 5)
    assert(findKthLargest([]int{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4) == 4)
    assert(findKthLargest([]int{1}, 1) == 1)
    assert(findKthLargest([]int{2, 2, 2, 2}, 2) == 2)
    assert(findKthLargest([]int{5, 3, 1, 4, 2}, 5) == 1)
    fmt.Println("all tests pass")
}

func main() { runTests() }

final class Solution {
    func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
        var heap = BinaryHeap<Int>(hasHigherPriority: <)
        for value in nums { heap.insert(value); if heap.count > k { _ = heap.removeRoot() } }
        return heap.peek!
    }
}

Where the time goes, line by line

Variables: n = number of elements in nums, k = the rank parameter.

Line	Per-call cost	Times executed	Contribution
L1 (loop)	$O(1)$	n	$O(n)$
L2 (heappush)	$O(log k)$	n	$O(n log k)$ ← dominates
L3 (heappop)	$O(log k)$	n - k	$O(n log k)$

The heap never exceeds k entries. Every push and pop costs $O(log k)$ . Since we process n elements, total cost is $O(n log k)$ .

Complexity

Time: $O(n log k)$ , driven by L2/L3.
Space: $O(k)$ .

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Quickselect (optimal average)

Partition-based selection; average linear time.

import random

def find_kth_largest(nums, k):
    # k-th largest = (n - k)-th smallest (0-indexed)
    target = len(nums) - k

    def partition(lo, hi):
        pivot = nums[random.randint(lo, hi)]  # L1: O(1) random pivot
        left, right = lo, hi
        i = lo
        while i <= right:                      # L2: three-way partition
            if nums[i] < pivot:
                nums[left], nums[i] = nums[i], nums[left]
                left += 1; i += 1
            elif nums[i] > pivot:
                nums[right], nums[i] = nums[i], nums[right]
                right -= 1
            else:
                i += 1
        return left, right   # pivot's final range [left, right]

    def quickselect(lo, hi):
        while True:
            if lo == hi:
                return nums[lo]
            l, r = partition(lo, hi)          # L3: O(hi - lo) per call
            if l <= target <= r:
                return nums[target]
            elif target < l:
                hi = l - 1
            else:
                lo = r + 1

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

function findKthLargest(nums: number[], k: number): number {
    const arr = nums.slice(); // avoid mutating input
    const target = arr.length - k;

    function partition(lo: number, hi: number): [number, number] {
        const pivotIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
        const pivot = arr[pivotIdx];  // L1: random pivot
        let left = lo, right = hi, i = lo;
        while (i <= right) {          // L2: three-way partition
            if (arr[i] < pivot) {
                [arr[left], arr[i]] = [arr[i], arr[left]];
                left++; i++;
            } else if (arr[i] > pivot) {
                [arr[right], arr[i]] = [arr[i], arr[right]];
                right--;
            } else {
                i++;
            }
        }
        return [left, right];
    }

    let lo = 0, hi = arr.length - 1;
    while (true) {
        if (lo === hi) return arr[lo];
        const [l, r] = partition(lo, hi);   // L3: O(hi - lo) per call
        if (l <= target && target <= r) return arr[target];
        else if (target < l) hi = l - 1;
        else lo = r + 1;
    }
}

package main

import (
    "fmt"
    "math/rand"
)

func findKthLargest(nums []int, k int) int {
    arr := make([]int, len(nums))
    copy(arr, nums)
    target := len(arr) - k

    partition := func(lo, hi int) (int, int) {
        pivot := arr[lo+rand.Intn(hi-lo+1)] // L1: O(1) random pivot
        left, right, i := lo, hi, lo
        for i <= right { // L2: three-way partition
            if arr[i] < pivot { arr[left], arr[i] = arr[i], arr[left]; left++; i++ } else if arr[i] > pivot { arr[right], arr[i] = arr[i], arr[right]; right-- } else { i++ }
        }
        return left, right
    }

    lo, hi := 0, len(arr)-1
    for {
        if lo == hi { return arr[lo] }
        l, r := partition(lo, hi) // L3: O(hi - lo) per call
        if l <= target && target <= r { return arr[target] } else if target < l { hi = l - 1 } else { lo = r + 1 }
    }
}

func assert(condition bool, msgs ...string) {
    if !condition { msg := "assertion failed"; if len(msgs) > 0 { msg = msgs[0] }; panic(msg) }
}

func runTests() {
    assert(findKthLargest([]int{3, 2, 1, 5, 6, 4}, 2) == 5)
    assert(findKthLargest([]int{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4) == 4)
    assert(findKthLargest([]int{1}, 1) == 1)
    assert(findKthLargest([]int{2, 2, 2, 2}, 2) == 2)
    assert(findKthLargest([]int{5, 3, 1, 4, 2}, 5) == 1)
    fmt.Println("all tests pass")
}

func main() { runTests() }

final class Solution {
    func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
        var values = nums
        let target = values.count - k
        var low = 0
        var high = values.count - 1
        while true {
            let pivot = values[high]
            var store = low
            for index in low..<high where values[index] <= pivot { values.swapAt(store, index); store += 1 }
            values.swapAt(store, high)
            if store == target { return values[store] }
            if store < target { low = store + 1 } else { high = store - 1 }
        }
    }
}

Where the time goes, line by line

Variables: n = number of elements in nums, k = the rank parameter.

Line	Per-call cost	Times executed	Contribution
L1 (random pivot)	$O(1)$	log n avg rounds	$O(log n)$
L2 (three-way partition)	$O(subarray size)$	log n avg rounds	$O(n)$ avg ← dominates
L3 (partition call)	$O(n)$ first round	log n avg	$O(n)$ avg

On average, each round halves the search space: n + n/2 + n/4 + … = 2n = $O(n)$ . With random pivot, worst case $O(n²)$ is extremely unlikely.

Complexity

Time: $O(n)$ average, $O(n²)$ worst case (mitigated by random pivot at L1).
Space: $O(1)$ extra (iterative loop avoids recursion).

The three-way partition handles duplicate values efficiently, important when the array contains many repeats.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

# Quick smoke tests, paste into a REPL or save as test_215.py and run.
# Uses the size-K min-heap approach (Approach 2).
import heapq

def find_kth_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

def _run_tests():
    # Examples from problem statement
    assert find_kth_largest([3,2,1,5,6,4], 2) == 5
    assert find_kth_largest([3,2,3,1,2,4,5,5,6], 4) == 4
    # k = 1: largest
    assert find_kth_largest([1], 1) == 1
    # All same
    assert find_kth_largest([2,2,2,2], 2) == 2
    # k = n: smallest
    assert find_kth_largest([5,3,1,4,2], 5) == 1
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

// Uses the size-K min-heap approach (Approach 2).
// See 215-kth-largest-element-in-an-array-approach2.ts for the full implementation.
console.assert(findKthLargest([3,2,1,5,6,4], 2) === 5);
console.assert(findKthLargest([3,2,3,1,2,4,5,5,6], 4) === 4);
console.assert(findKthLargest([1], 1) === 1);
console.assert(findKthLargest([2,2,2,2], 2) === 2);
console.assert(findKthLargest([5,3,1,4,2], 5) === 1);
console.log("all tests pass");

Summary

Approach	Time	Space
Sort	$O(n log n)$	$O(1)$
Size-K min-heap	$O(n log k)$	$O(k)$
Quickselect	$O(n)$ avg / $O(n²)$ worst	$O(1)$

The heap is the interview-safe answer. Quickselect is the “show you understand selection algorithms” answer. In practice, std-lib nlargest is often the fastest due to constant factors.

Heaps / Priority Queues, size-K min-heap
Arrays, in-place partitioning for quickselect

Divide and Conquer, split-solve-combine tactics for reducing a problem into independent smaller pieces.
Heap and Priority Queue, priority-frontier tactics for repeatedly extracting the smallest, largest, or most urgent item.
Top K, selection tactics for finding the largest, smallest, or most frequent K items without fully ordering everything.

215. Kth Largest Element in an Array (Medium)

Problem

Try it yourself

Approach 1: Brute force, sort, index

Approach 2: Size-K min-heap

Approach 3: Quickselect (optimal average)

Test cases

Summary

Related data structures

Related concepts