Leetcode 215. Kth Largest Element in an Array

Problem Explanation

The problem is to find the kth largest element in an unsorted array where k is a positive integer. The problem explicitly clarifies that the kth largest element is in sorted order, hence the kth largest element will not necessarily be the kth distinct element. The key challenge here is that we do not have a sorted array to begin with, and sorting an entire array can be costly(mostly O(nlogn)) in terms of time complexity.

For example, in the array [3,2,1,5,6,4] the 2nd largest element is 5. If you sort it in non-ascending order you get [6,5,4,3,2,1] and the 2nd element in the list is 5.

Approach

The solution provided utilizes a min heap, which is a tree data structure that satisfies the heap property where the parent node is less than or equal to its child nodes. This property allows us to always know which is the smallest element of a set in O(1) time complexity. We continually add elements from the numbers in the array to the heap, and if the size of the heap becomes larger than k (the desired largest element position), we pop out the smallest element in the heap. We continue this until we've checked all the elements in the array. At the end, the top of the heap will be the kth largest element.

The reason this works is because the heap is continually removing the smallest values and only the largest values remain. When we've finished iterating through the array, the smallest value in the heap is actually the kth largest value in the array, because all values smaller than it have already been popped.

Python Solution

1
2python
3import heapq
4class Solution:
5    def findKthLargest(self, nums: List[int], k: int) -> int:
6        minHeap = []
7        #Create a min heap of size k
8        for num in nums:
9            heapq.heappush(minHeap, num)
10            if len(minHeap) > k:
11                heapq.heappop(minHeap)
12        #At this point, the heap contains the k largest elements. The smallest of these k elements is at the top
13        return heapq.heappop(minHeap)

Java Solution

1
2java
3class Solution {
4    public int findKthLargest(int[] nums, int k) {
5        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
6
7        for (int num: nums) {
8            minHeap.offer(num);
9            if (minHeap.size() > k) {
10                minHeap.poll();
11            }
12        }
13
14        return minHeap.peek();
15    }
16}

JavaScript Solution

1
2javascript
3class Solution {
4    findKthLargest(nums, k) {
5        let minHeap = new MinBinaryHeap();
6        for (let i = 0; i < nums.length; i++) {
7            minHeap.push(nums[i]);
8            if (minHeap.length > k) {
9                minHeap.pop();
10            }
11        }
12        return minHeap.peek();
13    }
14}

C++ Solution

1
2c++
3class Solution {
4public:
5    int findKthLargest(vector<int>& nums, int k) {
6        priority_queue<int, vector<int>, greater<>> minHeap;
7
8        for (const int num : nums) {
9            minHeap.push(num);
10            if (minHeap.size() > k)
11                minHeap.pop();
12        }
13
14        return minHeap.top();
15    }
16};

C# Solution

1
2csharp
3public class Solution {
4    public int FindKthLargest(int[] nums, int k) {
5        var minHeap = new SortedSet<int>();
6
7        foreach (var num in nums) {
8            minHeap.Add(num);
9            if (minHeap.Count > k) 
10                minHeap.Remove(minHeap.Min);
11        }
12
13        return minHeap.Min;
14    }
15}

In each solution, we use the language's standard heap (priority queue data structure) to maintain a min heap. If at any time the size of our min-heap is greater than k, we pop the smallest element, ensuring that our heap only contains the k largest elements encountered thus far. At the end, the top of our heap contains the k-th largest element.In terms of time complexity, given N is the length of the input array, the overall time complexity of each solution is O(N log k). This is because, for each element in the array, we add it to our heap which costs O(log k) time.

The space complexity for each solution is O(k) as at most, we store k elements in our heap.

You can translate the solution to other languages that support heap/priority queue data structure. If the standard library doesn't have a heap data structure available, you can implement one using an array or a binary tree.

Heaps are a powerful data structure to be familiar with and this problem serves as a great example of how they can be used to efficiently find answers to problems that involve sorting or ordering.

In a real world application, you can use this kind of solution to answer questions like "What are the top K selling products in my e-commerce store?" or "Who are the K most active users in my application?". By using a heap-based solution instead of sorting the entire array, you can answer these questions more efficiently which can be important when dealing with large datasets or when performance is a critical component of your application.

Remember that these solutions assume that you have sufficient memory to hold the data. If your data is too large to fit into memory, you might need a solution based on external sorting which is a method of sorting that can handle massive amounts of data. However, that's a topic for another day. For now, it's good to note the efficiency of using a heap for this kind of problem.