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?


  • 0
    P

    Firstly, the heap size is always constant (2 + 3). Hence the space complexity is O(1). Since you are performing pop and push on a heap of constant size, push and pop become constant too (log constant). Hence time complexity is still O(n). This solution is good because it can be extended for more numbers if required - say max product of 4 or 5 numbers in which case you don't want to be maintaining so many max and min variables.


Log in to reply
 

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