215. Kth Largest Element in an Array - Detailed Explanation

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.

For example, if the array is sorted in descending order, the kth largest element is the element at index k-1.

This question is an instance of the Top K Elements pattern. In that pattern you never sort the whole input. You keep a heap of exactly k items, which is a structure that always hands you its smallest or largest member in constant time, and the heap holds the running answer as the scan proceeds. Several interview favorites reduce to it, and the summary of the most common LeetCode patterns shows where it sits among the rest.

Examples

Example 1

• Input: nums = [3, 2, 1, 5, 6, 4], k = 2.
• Output: 5.
• Explanation: When sorted in descending order, the array becomes [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: When sorted in descending order, the array becomes [6, 5, 5, 4, 3, 3, 2, 2, 1]. The 4th largest element is 4.

Approaches

Three approaches solve this problem, and they trade work against simplicity in different ways.

1. Sorting

• Idea: Sort the array in descending order and return the element at index k-1.
• Pros: Simple to implement, and hard to get wrong under pressure.
• Cons: Sorting the entire array takes O(n log n) time. That is more work than the question needs, since only one element is required.

2. Min heap (priority queue)

• Idea: Maintain a min heap of size k. Iterate through the array and add each element to the heap. If the heap size exceeds k, remove the smallest element. After processing all elements, the top of the heap is the kth largest element.
• Pros: Efficient when k is small relative to n. The time complexity is O(n log k).
• Cons: Requires additional space for the heap.

3. Quickselect

• Idea: Use the quickselect algorithm, which borrows the partition step from quicksort. Instead of sorting the whole array, partition it around a pivot, so that elements less than the pivot come before it and greater elements come after it. Then recurse only into the part that contains the kth largest element.
• Pros: Average time complexity of O(n), with no extra data structure.
• Cons: More complex to implement, and the worst case is O(n²) when the pivots split the array badly.

Detailed explanation of the min heap approach

1. Initialize a min heap: Create an empty min heap that will store up to k elements.

2. Process each element in the array:

   • For each element in nums, add it to the min heap.
   • If the heap size exceeds k, remove the smallest element, which is the root of the min heap.
   • The heap therefore always contains the k largest elements seen so far.

3. Final result: Once all elements are processed, the smallest element in the min heap is the kth largest element overall.

The whole method rests on one invariant: the root of a size-k min heap is the smallest of the k best values, which is exactly the kth largest. Design Gurus walks through this problem in the Kth Largest Element in an Array lesson of Grokking the Coding Mock Interview, in the format of a timed round.

Python code