Scalable solution using Priority Queue (Java)


  • 1
    V
    public class Solution {
        public int maximumProduct(int[] nums) {
            PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
            PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((a,b) -> b-a);
            
            for(int i=0; i<nums.length; i++) {
                int num = nums[i];
                
                if(num < 0) {
                    maxHeap.add(num);
                    if(maxHeap.size() > 3) maxHeap.poll();
                } else {
                    minHeap.add(num);
                    if(minHeap.size() > 3) minHeap.poll();
                }
            }
            
            int[] sorted = new int[6];
            int i = 2;
            int j = 3;
            while(!maxHeap.isEmpty()) {
                sorted[i--] = maxHeap.poll();
            }
            while(!minHeap.isEmpty()) {
                sorted[j++] = minHeap.poll();
            }
            
            int max = Math.max((sorted[i+1] * sorted[i+2] * sorted[j-1]), (sorted[j-1] * sorted[j-2] * sorted[j-3]));
            return max;
        }
    }
    

  • 0
    S

    @venkat Why use a priority queue which additional space, when sorting does the same job in O(n log n) while taking scalability into consideration?


Log in to reply
 

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