215. Kth Largest Element in an Array - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

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.

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

There are several approaches to solve this problem:

1. Sorting

Idea:
Sort the array in descending order and return the element at index k-1.
Pros:
Simple to implement.
Cons:
Sorting the entire array takes O(n log n) time, which may be more than needed if only one element is required.

2. Min Heap (Priority Queue)

Idea:
Maintain a min heap (priority queue) 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 Algorithm

Idea:
Use the Quickselect algorithm, which is similar to QuickSort. Instead of sorting the whole array, partition the array around a pivot so that elements less than the pivot come before it and elements greater come after it. Recurse into the part that contains the kth largest element.
Pros:
Average time complexity of O(n), though the worst-case is O(n²).
Cons:
More complex to implement, and the worst-case time complexity is not linear.

Detailed Explanation of the Min Heap Approach

Initialize a Min Heap:
Create an empty min heap that will store up to k elements.
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 (the root of the min heap).
- This way, the heap always contains the k largest elements seen so far.
Final Result:
Once all elements are processed, the smallest element in the min heap is the kth largest element overall.

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
- Sorting approach: O(n log n)
- Min Heap approach: O(n log k), since each insertion/deletion in the heap of size k takes O(log k).
- Quickselect approach: Average O(n), Worst-case O(n²).
Space Complexity:
- Sorting approach: O(1) if in-place, otherwise O(n).
- Min Heap approach: O(k).
- Quickselect approach: O(1) extra space if done in-place.

Common Mistakes and Edge Cases

Incorrect Heap Size:
Not maintaining the heap size at exactly k may lead to the wrong answer.
Handling Negative Numbers:
Ensure that negative numbers are correctly processed by the heap or quickselect.
Edge Case - Single Element:
When the array contains only one element, that element is the kth largest regardless of k (which will be 1).

Kth Smallest Element in a Sorted Matrix:
A problem that involves finding an element in a matrix using similar techniques.
Top K Frequent Elements:
Involves finding the k most frequent elements using heaps.
Median of Two Sorted Arrays:
Another selection problem that requires finding a specific order statistic.