Kth Largest Element in an Array

LeetCode 215: Kth Largest Element in an Array Solution & Explanation

Problem Overview

TL;DR: To solve LeetCode 215, we maintain a Min-Heap of size k to track the top k elements encountered so far; the root of this heap represents the $k$-th largest element.

The problem asks us to identify the $k$-th largest integer in an unsorted array nums. It is important to distinguish this from the $k$-th distinct element; duplicates count towards the ranking. For example, if the input is [3, 3, 3] and k=2, the answer is 3. The problem statement explicitly challenges us to solve this without sorting the entire array, making this a classic interview question for testing data structure proficiency.

Brute Force Approach for Kth Largest Element in an Array

The most intuitive way to solve the Kth Largest Element in an Array is to sort the entire array in descending order and select the element at index k-1 (or sort ascending and select index N-k).

Naive Pseudo-code

function findKthLargest(nums, k):
    sort(nums)  // Sorts in ascending order
    n = length(nums)
    return nums[n - k]

Complexity Analysis

• Time Complexity: $O(N \log N)$, where $N$ is the number of elements in the array. This is dominated by the sorting algorithm (e.g., Timsort or Quicksort).
• Space Complexity: $O(1)$ or $O(N)$ depending on the specific sorting implementation and whether it operates in-place.

Why this approach is suboptimal

While this solution is correct and often passes online judges, it fails the specific constraint mentioned in the problem description: "Can you solve it without sorting?". In an interview context, solving a selection problem with full sorting is considered inefficient because we perform unnecessary work. We order the entire array when we only care about the relationship between the top k elements and the rest.

Algorithm Strategy: Heap (Priority Queue) Patterns

1. Initialize a Min-Heap: Create a priority queue configured as a Min-Heap. This structure will maintain the invariant that it contains the $k$ largest elements processed so far.
2. Iterate through the Array: Loop through every number in nums.
3. Maintain Heap Size:
   • Push the current number onto the heap.
   • If the size of the heap exceeds k, remove the smallest element (the root). This step ensures that we discard the elements that are too small to be in the top k.
4. Result: After iterating through the entire array, the Min-Heap will contain exactly k elements. The element at the top of the Min-Heap is the smallest of these k giants, effectively making it the $k$-th largest element of the entire array.

Execution Flow

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

1. Initialize: Min-Heap pq = [].
2. Process 3: Push 3. Heap: [3]. Size is 1 ($< k$).
3. Process 2: Push 2. Heap: [2, 3]. Size is 2 ($= k$).
4. Process 1: Push 1. Heap: [1, 2, 3]. Size is 3 ($> k$). Pop min (1). Heap: [2, 3].
   • Logic: 1 is smaller than the current top 2 (2 and 3), so it is discarded.
5. Process 5: Push 5. Heap: [2, 3, 5]. Size is 3 ($> k$). Pop min (2). Heap: [3, 5].
   • Logic: 5 is larger than 2. 2 is no longer in the top 2.
6. Process 6: Push 6. Heap: [3, 5, 6]. Size is 3 ($> k$). Pop min (3). Heap: [5, 6].
   • Logic: 6 enters, 3 is evicted.
7. Process 4: Push 4. Heap: [4, 5, 6]. Size is 3 ($> k$). Pop min (4). Heap: [5, 6].
   • Logic: 4 is smaller than 5 and 6. It enters momentarily but is immediately the smallest, so it is popped.
8. Result: The top of the heap is 5. Correct.

Proof of Correctness

The algorithm maintains the invariant that at step $i$, the heap contains the $k$ largest elements from the subarray nums[0...i].

• Base Case: For the first $k$ elements, the heap simply stores them all.
• Inductive Step: Assume the heap contains the $k$ largest elements of nums[0...i-1]. Let $min\_top\_k$ be the root of the heap. When we process nums[i]:
  • If nums[i] <= min_top_k, then nums[i] is not larger than any of the current top $k$. It correctly does not displace any element (or it displaces itself immediately).
  • If nums[i] > min_top_k, then nums[i] is strictly larger than the smallest of the top $k$. Therefore, min_top_k is no longer in the top $k$ set for the subarray nums[0...i]. We remove min_top_k and include nums[i], restoring the invariant.

By induction, after processing $N$ elements, the heap contains the $k$ largest elements of the entire array. The root is the minimum of this set, which corresponds to the $k$-th largest value.

Pattern Reuse Notes

The Heap - Top K Elements pattern used in this LeetCode 215 Solution is highly versatile. It applies directly to several other popular interview questions:

• LeetCode 347: Top K Frequent Elements - Instead of element values, we push (frequency, value) pairs into the Min-Heap.
• LeetCode 451: Sort Characters By Frequency - Similar to Top K Frequent, but we construct a string from the heap results.
• LeetCode 506: Relative Ranks - Uses a heap to map scores to ranks (Gold, Silver, Bronze).
• LeetCode 703: Kth Largest Element in a Stream - This is the "live" version of LeetCode 215 where the array grows dynamically; the Min-Heap approach is the standard optimal solution here.

Reference Implementation

C++ Solution for LeetCode 215

1#include <vector>
2#include <queue>
3
4class Solution {
5public:
6    int findKthLargest(std::vector<int>& nums, int k) {
7        // Min-heap to store the top k elements
8        // std::priority_queue is a max-heap by default, so we use greater<int>
9        std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
10        
11        for (int num : nums) {
12            minHeap.push(num);
13            
14            // If heap size exceeds k, remove the smallest element
15            if (minHeap.size() > k) {
16                minHeap.pop();
17            }
18        }
19        
20        // The root of the min-heap is the kth largest element
21        return minHeap.top();
22    }
23};

Java Solution for LeetCode 215

1import java.util.PriorityQueue;
2
3class Solution {
4    public int findKthLargest(int[] nums, int k) {
5        // Java's PriorityQueue is a Min-Heap by default
6        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
7        
8        for (int num : nums) {
9            minHeap.add(num);
10            
11            // Maintain exactly k elements in the heap
12            if (minHeap.size() > k) {
13                minHeap.poll();
14            }
15        }
16        
17        // The top of the heap is the kth largest element
18        return minHeap.peek();
19    }
20}

Python Solution for LeetCode 215

1import heapq
2
3class Solution:
4    def findKthLargest(self, nums: list[int], k: int) -> int:
5        min_heap = []
6        
7        for num in nums:
8            # Push the current number onto the heap
9            heapq.heappush(min_heap, num)
10            
11            # If the heap grows larger than k, remove the smallest element
12            if len(min_heap) > k:
13                heapq.heappop(min_heap)
14                
15        # The smallest element in the heap of size k is the kth largest overall
16        return min_heap[0]