Kth Largest Element in an Array

Difficulty: Medium

Problem

Given an integer array nums and an integer k, return the element that would sit at position k when the values are ranked from biggest to smallest. Duplicates count separately (it is not the kth distinct value). Can you do it without fully sorting?

Example

Input: nums = [7, 10, 4, 3, 20, 15], k = 3
Output: 10
Explanation: Sorted, the array is [3, 4, 7, 10, 15, 20]. From the top, 20 is 1st, 15 is 2nd and 10 is 3rd largest.

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)

Pseudocode

function findKthLargest(nums, k):
    // Using min-heap of size k
    heap = MinHeap()
    for num in nums:
        heap.push(num)
        if heap.size > k:
            heap.pop()  // remove smallest
    return heap.top()  // kth largest

Hints

  • Think about what a min-heap of size k maintains. It always has the k largest elements seen so far
  • The smallest element in a min-heap of size k is the kth largest overall
  • You can also use QuickSelect for O(n) average time

Complexity questions

What is the time complexity of scanning the array k times to find the kth largest?

O(n × k). Each pass scans all n elements to find the current max, and we do k passes. Total: O(n × k).

What is the time complexity of the min-heap approach?

O(n log k). We process n elements, each requiring O(log k) for heap push/pop. Total: O(n log k).

What is the space complexity of the min-heap approach?

O(k). The heap holds at most k elements, O(k) space.

Check your understanding of Kth Largest Element in an Array

For nums = [3, 2, 1, 5, 6, 4], what is the 2nd largest element?

5 (the 2nd largest). Sorted in descending order: [6, 5, 4, 3, 2, 1]. The 2nd element is 5.

For nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], what is the 4th largest?

4. Sorted descending: [6, 5, 5, 4, 3, 3, 2, 2, 1]. The 4th element is 4. Note: duplicates count as separate positions.

Why is a min-heap of size k useful here?

It stores the k largest elements, with the smallest of them (the kth largest) on top for O(1) access. A min-heap of size k keeps the k largest elements. The heap's minimum is the kth largest, exactly what we need. When a new element is bigger than the heap min, it replaces it.

Related problems

Keep practising