215. Kth Largest Element in an Array

Quick Identifier

Topic: heap-priority-queue
Pattern: Top-K / Heap
Difficulty: Medium
Companies: Amazon, Meta, Google, Microsoft, Bloomberg
Frequency: Very High
LeetCode: 215

Quick Sights

Time Complexity: O(n) from the optimal approach.
Space Complexity: O(1) from the optimal approach.
Core Mechanism: Given integer array nums and k, return the element that would be at index n-k if the array were sorted ascending (the kth largest in 1-based sense).

Concept Explanation

Given integer array nums and k, return the element that would be at index n-k if the array were sorted ascending (the kth largest in 1-based sense).

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

kth largest in a static array
Full sort is acceptable but not optimal for large n with small k
Quickselect vs min-heap tradeoff

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — sort descending, pick index k-1 — O(n log n) time.
Better — min-heap of size k — O(n log k) time, O(k) space.
Optimal (average) — quickselect on arbitrary array — O(n) expected time, O(1) space with careful partition.

Optimal Solution

Go

import (
	"container/heap"
)

type IntMinHeap []int

func (heapSlice IntMinHeap) Len() int           { return len(heapSlice) }
func (heapSlice IntMinHeap) Less(left, right int) bool {
	return heapSlice[left] < heapSlice[right]
}
func (heapSlice IntMinHeap) Swap(left, right int) {
	heapSlice[left], heapSlice[right] = heapSlice[right], heapSlice[left]
}

func (heapSlice *IntMinHeap) Push(value any) {
	*heapSlice = append(*heapSlice, value.(int))
}

func (heapSlice *IntMinHeap) Pop() any {
	old := *heapSlice
	length := len(old)
	value := old[length-1]
	*heapSlice = old[0 : length-1]
	return value
}

func findKthLargest(nums []int, k int) int {
	minHeap := &IntMinHeap{}
	heap.Init(minHeap)
	for _, value := range nums {
		heap.Push(minHeap, value)
		if minHeap.Len() > k {
			heap.Pop(minHeap)
		}
	}
	return (*minHeap)[0]
}

JavaScript

class MinHeap {
  constructor() {
    this.data = [];
  }

  size() {
    return this.data.length;
  }

  peek() {
    return this.data[0];
  }

  push(value) {
    this.data.push(value);
    this.bubbleUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) {
      return undefined;
    }
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.data[index] >= this.data[parentIndex]) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  bubbleDown(index) {
    const length = this.data.length;
    while (true) {
      const leftChild = index * 2 + 1;
      const rightChild = index * 2 + 2;
      let smallest = index;
      if (leftChild < length && this.data[leftChild] < this.data[smallest]) {
        smallest = leftChild;
      }
      if (rightChild < length && this.data[rightChild] < this.data[smallest]) {
        smallest = rightChild;
      }
      if (smallest === index) {
        break;
      }
      this.swap(index, smallest);
      index = smallest;
    }
  }

  swap(leftIndex, rightIndex) {
    const temp = this.data[leftIndex];
    this.data[leftIndex] = this.data[rightIndex];
    this.data[rightIndex] = temp;
  }
}

function findKthLargest(nums, k) {
  const minHeap = new MinHeap();
  for (const value of nums) {
    minHeap.push(value);
    if (minHeap.size() > k) {
      minHeap.pop();
    }
  }
  return minHeap.peek();
}