# C++ solution in O(n) using priority_queue

• I see most of the solutions are sorting the entire input array, which makes the codes run in `O(nlogn)` time. Here is my `O(n)` solution using two `priority_queue<int>`, a min heap to keep the largest 3 elements and a max heap for the smallest 2 elements.

``````int maximumProduct(vector<int>& nums) {
priority_queue<int> max_heap;
priority_queue<int, vector<int>, greater<int>> min_heap;
for (int num : nums)
{
if (max_heap.size() < 2 || num < max_heap.top())
{
if (max_heap.size() == 2)
max_heap.pop();
max_heap.push(num);
}
if (min_heap.size() < 3 || num > min_heap.top())
{
if (min_heap.size() == 3)
min_heap.pop();
min_heap.push(num);
}
}
int b = max_heap.top();
max_heap.pop();
int a = max_heap.top();
int c = min_heap.top();
min_heap.pop();
int d = min_heap.top();
min_heap.pop();
int e = min_heap.top();
return max(a * b * e, c * d * e);
}
``````

• Same idea, but using two multiset instead.
Remove the smallest (first) element in "largest" multiset and largest (last) element in "smallest" multiest when their size becomes greater than 3 and 2 respectively.

``````int maximumProduct(vector<int>& nums) {
multiset<int> largest;
multiset<int> smallest;

for(int i: nums){
largest.insert(i);
smallest.insert(i);
if(largest.size() > 3)
largest.erase(largest.begin());
if(smallest.size() > 2)
smallest.erase(prev(smallest.end()));
}

int res1 = 1, res2 = *(largest.rbegin());
for(int i : largest)
res1 *= i;
for(int i : smallest)
res2 *= i;

return max(res1, res2);
}
``````

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