LeetCode — Kth Largest Element in an Array

Problem Link: https://leetcode.com/problems/kth-largest-element-in-an-array/

Photo by David Edelstein on Unsplash

Problem Description: Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Approach Used: Heap, Priority Queue

Explanation: The most naive approach to solve this problem would to simply sort the array and return the element at (n-k)th position in O(N log N) time.
But we can do better than that. This problem is a very straight forward and one of the most basic questions of the heap data structure. Heap is a data structure which is like a binary tree with one special condition that every parent node will be greater (max-heap) or smaller(min-heap) than both it’s children. If we remove any node from this heap then we check in all its children and their subtrees then heap condition is not be violated. If it is, then we again reconstruct the heap from that point. Which means that if we take out the root node from the max-heap k times, it will give the top k or k maximum values in the heap. We will use this to solve our problem. We can easily implement a heap, but since Java provides another Collection which internally implements heap, we will use that to solve our problem. The data structure is called the Priority Queue. By default, the Priority Queue is a min-heap but can be easily converted to a max heap. I’ve solved this problem with both min heap and max heap for better understanding.

Code: (Java)

public int findKthLargestUsingMinHeap(int[] nums, int k){
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(int i=0; i<nums.length; i++)
            minHeap.add(nums[i]);
        for(int i=1; i<=nums.length-k; i++)
            minHeap.poll();
        
        return minHeap.poll();
    }
    public int findKthLargestUsingMaxHeap(int[] nums, int k){
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for(int i=0; i<nums.length; i++)
            maxHeap.add(nums[i]);
        for(int i=1; i<=k-1; i++)
            maxHeap.poll();
        
        return maxHeap.poll();
    }
    public int findKthLargestUsingSorting(int[] nums, int k){
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
    public int findKthLargest(int[] nums, int k) {
        // return findKthLargestUsingMinHeap(nums, k);
        return findKthLargestUsingMaxHeap(nums, k);
        // return findKthLargestUsingSorting(nums, k);
    }

Complexity:
Space Complexity: O(n). Since a priority queue of n nodes is made for every test case.
Time Complexity: O(n + klogn). To insert nodes (construct tree) in a heap and then to iteratively remove (reconstruct tree).