C++ || 7 different approaches || lots of STL and the optimal solution || clean code
If you are looking for the best solution to the problem skip to approach 7. That said the other approach outline some different ideas that could be useful in si
If you are looking for the best solution to the problem skip to approach 7. That said the other approach outline some different ideas that could be useful in similar situations.

Please let me know if you have more ideas or suggestions for one of the approaches below.

**Please upvote if you learned something new. :)**


# Approach 1: brute force

The length of the input is small enough that we can just use brute force.

```cpp
    static int maxProduct(const vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < size(nums); ++i)
            for (int j = i + 1; j < size(nums); ++j)
                ans = max(ans, (nums[i] - 1) * (nums[j] - 1));

        return ans;
    }
```

**Complexity Analysis**
  * Time complexity: $$O(n^2)$$
  * Space complexity: $$O(1)$$


# Approach 2: std::sort

If we sort descending the answer is based on the first two elements.

```cpp
    static int maxProduct(vector<int>& nums) {
        sort(begin(nums), end(nums), greater<int>());
        return (nums[0] - 1) * (nums[1] - 1);
    }
```

**Complexity Analysis**
  * Time complexity: $$O(n \log n)$$
  * Space complexity: $$O(1)$$


# Approach 3: std::partial_sort

We don't need to sort all of ```nums```, we only care about the first two elements, hence a ```std::partial_sort``` does the trick.

```cpp
    static int maxProduct(vector<int>& nums) {
        partial_sort(begin(nums), next(begin(nums), 2), end(nums), greater<int>());
        return (nums[0] - 1) * (nums[1] - 1);
    }
```

**Complexity Analysis**
  * Time complexity: $$O(n \log 2)$$ see details for std::partial_sort
  * Space complexity: $$O(1)$$


# Approach 4: std::nth_element

Multiplication is commutative, therefore we don't care about the order of the two largest elements and can use quick select to find them.

```cpp
    static int maxProduct(vector<int>& nums) {
        nth_element(begin(nums), next(begin(nums), 2), end(nums), greater<int>());
        return (nums[0] - 1) * (nums[1] - 1);
    }
```

**Complexity Analysis**
  * Time complexity: $$O(n)$$ for quick select
  * Space complexity: $$O(1)$$


# Approach 5: std::priority_queue (min heap)

That that this approach of using a min heap is keeping the min heap at a boundest size, i.e. there is no need to push all of ```nums``` onto the heap just to pull the largest two from a max heap.

```cpp
    static int maxProduct(const vector<int>& nums) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int num : nums) {
            if (size(pq) < 2 || num >= pq.top()) {
                pq.push(num);
                if (size(pq) == 3) pq.pop();
            }
        }
        const int max1 = pq.top(); pq.pop();
        return (max1 - 1) * (pq.top() - 1);
    }
```

**Complexity Analysis**
  * Time complexity: $$O(n \log 2)$$ so basically $$O(n)$$
  * Space complexity: $$O(1)$$ since the size of the min heap is bounded

# Approach 6: std::make_heap / std::pop_heap

Instead of creating an extra heap (```std::priority_queue```) we can create a max heap in place of ```nums``` and modify this heap.

```cpp
    static int maxProduct(vector<int>& nums) {
        make_heap(begin(nums), end(nums));
        const int max1 = nums.front();
        pop_heap(begin(nums), end(nums));
        return (max1 - 1) * (nums.front() - 1);
    }
```

@fusu06ck610 pointet out that this could also look like this, as ```pop_heap``` moves the largest element to the back of ```nums```. Thanks!

```cpp
    static int maxProduct(vector<int>& nums) {
        make_heap(begin(nums), end(nums));
        pop_heap(begin(nums), end(nums));
        return (nums.back() - 1) * (nums.front() - 1);
    }
```

**Complexity Analysis**
  * Time complexity: $$O(n)$$ for make_heap and $$O(\log n)$$ for pop_heap.
  * Space complexity: $$O(1)$$

# Approach 7: biggest and second biggest

This is the obvious solution for the problem, and the solution you should probably reach for.

```cpp
    static int maxProduct(const vector<int>& nums) {
        int m1 = 0;
        int m2 = 0;
        for (int num : nums) {
            if (num >= m1) {
                m2 = m1;
                m1 = num;
            } else if (num > m2) {
                m2 = num;
            }
        }
        return (m1 - 1) * (m2 - 1);
    }
```

FWIW I learned something from @votrubac's post on this topic, which is a nice of use ```std::exchange``` and instead of

```cpp
            if (num >= m1) {
                m2 = m1;
                m1 = num;
            }
```

@votrubac does the following, which I find really neat:

```cpp
            if (num >= m1) {
                m2 = exchange(m1, num);
            }
```

**Complexity Analsysis**
  * Time complexity: $$O(n)$$
  * Space complexity: $$O(1)$$

_As always: Feedback, questions, and comments are welcome. Leaving an upvote sparks joy! :)_

**p.s. Join us on the [LeetCode The Hard Way Discord Server](https://discord.gg/hFUyVyWy2E)!**
['C']