Easy Java Solution using Priority Queue and Comparator (18ms)


  • 0
    L

    This is a very similar approach to solving the sliding window problem (maximum sliding window), where we use a priority queue to keep things ordered.

    We use a Comparator function that implements the compare method, which is called by the Priority Queue when a new number is added. This allows us to modify the default behavior of comparing integers in natural order (i.e ascending)

    I decided to share a solution since I seen only a few somewhat similar methods of solving. Plus I wanted to offer some explanation.

    The run time of this will ne O(n + k), since we have to iterate though the entire array of integers, and then remove k-1 largest elements. The priority queue allows for log (k) insertions. Do correct me if I am wrong.

    Note for the newer Java users, the weird function inside a function syntax you see isn't too complicated. We're basically writing an anonymous function (function without a name) nested inside a Comparator() object, since one of the requirements of Comparator is to implement public int compare(T a, T b). (It is an abstract method that must be implemented else the Java compiler will not allow you to proceed.

    public class Solution {
        public int findKthLargest(int[] nums, int k) {
            int len = nums.length;
            // if(len == 0) return 0; //we get to assume k is always valid
            Queue<Integer> pq = new PriorityQueue(nums.length,
                                    new Comparator<Integer>(){ 
                                            public int compare(Integer a, Integer b) {
                                                return Integer.compare(b, a);
                                            }
                                    });
            for(int num : nums)
                pq.offer(num);
        
            int kth = 0;
            for(int i = 0; i < k; i++)
                kth = pq.poll();
        
            return kth;
        }
    }

  • 3
    G

    You can just use the normal order. and keep the queue's size under k by polling out the min when exceed, then the front of the queue will always be the kth largest element;

    And just for short code, your comparator can use Collections.reverseOrder() instead.

       public class Solution {
            public int findKthLargest(int[] nums, int k) {
                PriorityQueue<Integer> minHeap = new PriorityQueue(k+1);
                for (int i : nums) {
                    minHeap.offer(i);
                    if (minHeap.size() > k) minHeap.poll();
                }
                return minHeap.poll();
            }
        }

  • 0
    P

    Since we are removing elements from the heap the moment the size exceeds k (as done by minHeap.size() > k), is it necessary to create that heap with a size of k+1 ?

    I created a normal heap and it passed OJ -
    public int findKthLargest(int[] nums, int k){
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    for(int i = 0; i < nums.length; i++){
    minHeap.offer(nums[i]);
    if(minHeap.size() > k)
    minHeap.poll();
    }
    return minHeap.poll();
    }

    PS: I apologize if the code doesn't come out properly edited. I am new here and don't know where to find the option of keeping the indentations in the code. Any help would be appreciated :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.