Without Sorting || O(n) Solution || Faster than 99.3% || Priority Queue
Complexity\r\n- Time complexity:\r\nO(n) Add your time complexity here, e.g. O(n) \r\n\r\n- Space complexity:\r\nO(1) Add your space complexity here, e.g. O(n) 
# Complexity\r\n- Time complexity:\r\n$$O(n)$$<!-- Add your time complexity here, e.g. $$O(n)$$ -->\r\n\r\n- Space complexity:\r\n$$O(1)$$<!-- Add your space complexity here, e.g. $$O(n)$$ -->\r\n\r\n# Code\r\n```\r\nclass Solution {\r\npublic:\r\n    int maxProductDifference(vector<int>& nums) {\r\n        priority_queue<int> maxpq;\r\n        priority_queue<int,vector<int>,greater<int>> minpq;\r\n        maxpq.push(nums[0]);maxpq.push(nums[1]);\r\n        minpq.push(nums[0]);minpq.push(nums[1]);\r\n        for(int  i=2;i<nums.size();i++){\r\n            int curr=nums[i];\r\n            if(curr>minpq.top()){\r\n                minpq.pop();\r\n                minpq.push(curr);\r\n            }\r\n            if(curr<maxpq.top()){\r\n                maxpq.pop();\r\n                maxpq.push(curr);\r\n            }\r\n        }\r\n        int x=maxpq.top(),a=minpq.top();\r\n        maxpq.pop();minpq.pop();\r\n        int y=maxpq.top(),b=minpq.top();\r\n        return (a*b)-(x*y);\r\n    }\r\n};\r\n```
['Array', 'Heap (Priority Queue)', 'C++']