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;
        }
    }
    

Log in to reply
 

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