C++ || 6 different approaches || sort, partial_sort, nth_element, linear scan, heap
Please let me know if you came up with yet another solution to this problem.\n\n# Approach 1: std::sort()\n\nThe obvious solution is to sort nums and take the l
Please let me know if you came up with yet another solution to this problem.\n\n# Approach 1: std::sort()\n\nThe obvious solution is to sort ```nums``` and take the last two and the first two elements.\n\n```cpp\n    static int maxProductDifference(vector<int>& nums) {\n        sort(begin(nums), end(nums));\n        return nums[size(nums) - 1] * nums[size(nums) - 2] - nums[0] * nums[1];\n    }\n```\n\n**Complexity Analysis**\n  * Time Complexity: $$O(n \\log n)$$ -- because of the ```std::sort```.\n  * Space Complexity: $$O(1)$$\n\n# Approach 2: std::partial_sort() 2x\n\nWe don\'t need to sort all of ```nums```, only a partial sort to get the smallest two numbers and the largest two numbers is enough.\n\n```cpp\n    static int maxProductDifference(vector<int>& nums) {\n        partial_sort(begin(nums), next(begin(nums), 2), end(nums));\n        partial_sort(next(begin(nums), 2), next(begin(nums), 4), end(nums), greater<>());\n        return nums[2] * nums[3] - nums[0] * nums[1];\n    }\n```\n\n**Complexity Analysis**\n  * Time Complexity: According to cppreference.com the time complexity for std::partial_sort is approcimatly _(last - first) log (middle - first)_. In our case _(last - first)_ is _n_ and _(middle - first)_ is _2_ hence we have $$O(n \\log 2)$$ so basically $$O(n)$$.\n  * Space Complexity: $$O(1)$$\n\n# Approach 3: std::nth_element() 2x\n\nMultiplication is commutative, i.e. it doesn\'t matter in which order we multiple the two largest and the two smallest element. With that the don\'t even need to be sorted.\n\n```cpp\n    static int maxProductDifference(vector<int>& nums) {\n        nth_element(begin(nums), next(begin(nums), 2), end(nums));\n        nth_element(next(begin(nums), 2), next(begin(nums), 4), end(nums), greater<>());\n        return nums[2] * nums[3] - nums[0] * nums[1];\n    }\n```\n\n**Complexity Analysis**\n  * Time Complexity: $$O(n)$$ for quick select\n  * Space Complexity: $$O(1)$$\n\n# Approach 4: linear scan for first and second min / max\n\nThe solutions so far have modified ```nums```. We can also just scan through ```nums``` and keep track of the first and second minimum / maximum element.\n\n\n```cpp\n    static int maxProductDifference(const vector<int>& nums) {\n        int mx1 = numeric_limits<int>::min();\n        int mx2 = numeric_limits<int>::min();\n        int mn1 = numeric_limits<int>::max();\n        int mn2 = numeric_limits<int>::max();\n        for (const int n : nums) {\n            if (n > mx1) {\n                mx2 = mx1;\n                mx1 = n;\n            } else if (n > mx2) {\n                mx2 = n;\n            }\n            if (n < mn1) {\n                mn2 = mn1;\n                mn1 = n;\n            } else if (n < mn2) {\n                mn2 = n;\n            }\n        }\n        return mx1 * mx2 - mn1 * mn2;\n    }\n```\n\n**Complexity Analysis**\n  * Time Complexity: $$O(n)$$\n  * Space Complexity: $$O(1)$$\n\n# Approach 5: sort first 4 element and then linear scan\n\nThis is based on a solution from @ZX007PI. With this tweak only of one series of if / else instead of two like in solution 4, and we could argue this safes a branch. This variant of approach 4 modifies the input again.\n\n```cpp\n   static int maxProductDifference(vector<int>& nums) {\n        sort(begin(nums), next(begin(nums), 4));\n        int mx1 = nums[3];\n        int mx2 = nums[2];\n        int mn1 = nums[0];\n        int mn2 = nums[1];\n        for (int i = 4; i < size(nums); ++i) {\n            const int n = nums[i];\n            if (n >= mx1) {\n                mx2 = mx1;\n                mx1 = n;\n            } else if (n > mx2) {\n                mx2 = n;\n            } else if (n <= mn1) {\n                mn2 = mn1;\n                mn1 = n;\n            } else if (n < mn2) {\n                mn2 = n;\n            }\n        }\n        return mx1 * mx2 - mn1 * mn2;\n    }\n```\n\n**Complexity Analysis**\n  * Time Complexity: $$O(n)$$ we only sort 4 elements so the complexity remains linear.\n  * Space Complexity: $$O(1)$$\n\n# Approach 6: min / max heap\n\nIt\'s maybe a bit of an overkill to use a heap to solve this problem, but why not. I have seen some variants that push all elements on the the heap (```priority_queue```) without limiting the size to two elements, but that\'s a waste as we can keep the size of the heap bounded, which leads to better time / space complexity.\n\n```cpp\n   static int maxProductDifference(const vector<int>& nums) {\n        // The largest element will be on top and we will always\n        // pull of the largest element and it will result in having\n        // the smallest element remaining.\n        priority_queue<int> max_heap;\n        // ... and the other way around for the min heap.\n        priority_queue<int, vector<int>, greater<>> min_heap;\n        for (const int n : nums) {\n            max_heap.push(n);\n            if (size(max_heap) == 3) {\n                max_heap.pop();\n            }\n            min_heap.push(n);\n            if (size(min_heap) == 3) {\n                min_heap.pop();\n            }\n        }\n        const int mn1 = max_heap.top(); max_heap.pop();\n        const int mn2 = max_heap.top();\n        const int mx1 = min_heap.top(); min_heap.pop();\n        const int mx2 = min_heap.top();\n       \n        return mx1 * mx2 - mn1 * mn2;\n    }\n```\n\nThere is a variant to this solution where we only push on to the heap if that would actually make a different, either because the heap as fewer than 2 elments or the top element is other smaller or bigger so inserting would actually make a difference. The loop would like this:\n\n```cpp\n        for (const int n : nums) {\n            if (size(max_heap) < 2 || n < max_heap.top()) {\n                max_heap.push(n);\n                if (size(max_heap) == 3) max_heap.pop();\n            }\n            if (size(min_heap) < 2 || n > min_heap.top()) {\n                min_heap.push(n);\n                if (size(min_heap) == 3) min_heap.pop();\n            }\n        }\n```\n\n\n**Complexity Analysis**\n  * Time Complexity: $$O(n)$$ we do at most 2 comparisons per heap.\n  * Space Complexity: $$O(1)$$\n\n_As always: Feedback, questions, and commenst are welcome. Please upvote if you like the post._\n\n**p.s. Join us on the [LeetCode The Hard Way Discord Server](https://discord.gg/Nqm4jJcyBf)!**
['C', 'Sorting', 'Heap (Priority Queue)']