ToolMight LogoToolMight
MediumHeap & Priority QueueArrays & HashingPattern: Min-Heap Top-KPattern: Quickselect Partitioning

Kth Largest Element in an Array

Find the kth largest element in an unsorted array. The premier problem for learning Min-Heap bounded tracking and Quickselect partitioning.

Problem Statement

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?

Examples & Constraints

Example 1
Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Explanation: Sorted in descending order: [6, 5, 4, 3, 2, 1]. The 2nd largest element is 5.
Example 2
Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4
Explanation: Sorted in descending order: [6, 5, 5, 4, 3, 3, 2, 2, 1]. The 4th largest element is 4.
Constraints
  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Min-Heap of Size K (Streaming Pattern)

Optimal Approach
Time:O(n log k)
Space:O(k)

Maintain a Min-Heap of capacity K. Stream numbers into the heap and pop the smallest whenever size exceeds K. The root will always hold the Kth largest element in O(n log k) time.

Time ComplexityO(n log k)

Each of the N elements is pushed into a heap of size at most K. Heap push and pop operations take O(log k) time. For k << n, this is much faster than full sorting O(n log n).

Space ComplexityO(k)

The min-heap stores at most K + 1 elements at any point in time.

Underlying algorithmic logic

The Invariant: The Bounded VIP Lounge

Instead of sorting the entire array of size N in O(n log n) time, think of a VIP room that only holds K people:

  1. A Min-Heap keeps the smallest of its current members at the top (root) in O(1) peek time.
  2. For each number num in nums:
  • Push num into the Min-Heap.
  • If the heap size exceeds k, pop the top element.
  • What was popped? The smallest value among the top K + 1 elements!
  1. After processing all N elements, the heap contains the K largest elements seen across the entire array.
  2. Who is at the top of this Min-Heap? The smallest among the K largest elements — which is mathematically the Kth largest element!

Why Engineers Love This in Production

This approach is a streaming algorithm. If the input stream contains 10 billion numbers but you only need the Top-10 (k = 10), you do not need to store 10 billion items in memory! You only need a 10-element heap, using O(k) space regardless of stream length.

Step-by-step execution walkthrough

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

Initialize empty Min-Heap of capacity 2. Stream elements one by one.

heap = []
2
Stream 3, 2

Push 3 then 2. Heap size is 2. Top (smallest) is 2.

heap = [2, 3]
3
Stream 1

Push 1 -> heap = [1, 3, 2]. Size exceeds 2! Pop root (1).

heap = [2, 3]
4
Stream 5, 6, 4

Push 5, pop 2 -> [3, 5]. Push 6, pop 3 -> [5, 6]. Push 4, pop 4 -> [5, 6].

Final heap: [5, 6]. Root is 5 -> Result: 5
Advantages
  • •Optimal O(k) memory footprint
  • •Streams data without requiring all items in memory simultaneously
Trade-offs
  • •O(n log k) runtime is slightly slower than optimal average O(n) Quickselect

Code Implementations

Copy & paste production-ready solutions for Min-Heap of Size K (Streaming Pattern) in your language of choice

File: solution.py
Python
import heapq
def find_kth_largest(nums: list[int], k: int) -> int:
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    return min_heap[0]
if __name__ == "__main__":
    test1 = [3, 2, 1, 5, 6, 4]
    k1 = 2
    test2 = [3, 2, 3, 1, 2, 4, 5, 5, 6]
    k2 = 4
    print("test1 2nd largest:", find_kth_largest(test1, k1))
    print("test2 4th largest:", find_kth_largest(test2, k2))
Interactive visualizer available

Understand Heap & Priority Queue Visually

Understand min and max heap properties, tree structure balance, and heapify up/down actions. Test live edge cases and watch memory state transitions step-by-step.

Launch Heap & Priority Queue Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyArrays & Hashing
Visualizer

Contains Duplicate

Determine if any value appears at least twice in an integer array. A foundational problem for mastering constant-time hash lookups vs sorting trade-offs.

2 approaches(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Valid Anagram

Determine whether two strings have the exact same character frequencies. A core problem demonstrating the power of fixed-size frequency buckets over O(n log n) sorting.

2 approaches(O(n))
Learn logic