Kth Largest Element in an Array

Difficulty: Medium

Problem

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. Can you solve it without sorting?

Example

Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Explanation: The sorted array is [1, 2, 3, 4, 5, 6]. The 2nd largest element is 5.

Brute-force approach

Traverse the array k times. In each pass, find the current maximum by scanning every element, mark it as used, and repeat. The kth maximum found is the answer.

Steps

  1. Repeat k times:
  2. Traverse the array to find the current maximum
  3. Record the maximum value and its index
  4. Mark that index as used (-Infinity)
  5. Return the last maximum found (kth largest)

Time complexity: O(n × k) · Space complexity: O(1)

Trade-offs

  • Scans the entire array k times → O(n × k) which is O(n²) when k ≈ n
  • Modifies the original array (marks elements as -∞)
  • Much slower than heap approach O(n log k) for large inputs

Optimal approach

Key insight: A min-heap of size k always holds the k largest elements seen so far. Its minimum (top) is the kth largest — exactly our answer.

Use a min-heap of size k. Process each element: if the heap has fewer than k elements, push it. If the new element is larger than the heap minimum, replace the minimum. The heap minimum is the kth largest.

Steps

  1. Initialize an empty min-heap
  2. For each number in nums:
  3. Push it onto the heap
  4. If heap size > k, pop the minimum
  5. Return the heap top (minimum of k largest = kth largest)

Time complexity: O(n log k) · Space complexity: O(k)