C++ solution in O(n) using priority_queue


  • 0

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

  • 0
    J

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

Log in to reply
 

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