public class Solution {
public int maximumProduct(int[] nums) {
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((a,b) > ba);
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[j1]), (sorted[j1] * sorted[j2] * sorted[j3]));
return max;
}
}
Scalable solution using Priority Queue (Java)


@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?

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.