# Maximum Product of Two Elements in an Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/maximum-product-of-two-elements-in-an-array
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Samsung](https://scaleengineer.com/companies/samsung)
---
## Problem
Given the array of integers `nums`, you will choose two different indices `i` and `j` of that array. _Return the maximum value of_ `(nums[i]-1)*(nums[j]-1)`. 

**Example 1:**

**Input:** nums = [3,4,5,2]
**Output:** 12 
**Explanation:** If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 

**Example 2:**

**Input:** nums = [1,5,4,5]
**Output:** 16
**Explanation:** Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.

**Example 3:**

**Input:** nums = [3,7]
**Output:** 12

**Constraints:**

* `2 <= nums.length <= 500`
* `1 <= nums[i] <= 10^3`

# Approaches
## Brute Force
This approach involves checking every possible pair of distinct elements in the array. We use nested loops to iterate through all pairs `(i, j)` where `i` is not equal to `j`. For each pair, we calculate the product `(nums[i]-1)*(nums[j]-1)` and keep track of the maximum product found so far.
**Time:** O(n^2), where n is the number of elements in `nums`. The nested loops result in a quadratic number of comparisons. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** Simple to understand and implement.; Guaranteed to find the correct answer as it checks all possibilities.
**Cons:** Highly inefficient for large arrays due to its O(n^2) time complexity.; Performs a lot of redundant calculations.
### Explanation
We initialize a variable `maxProduct` to 0. The outer loop iterates from the first element to the second-to-last element (index `i`). The inner loop iterates from the element after `i` to the last element (index `j`). This structure ensures that we consider each pair of distinct indices exactly once. Inside the inner loop, we compute the product `(nums[i]-1) * (nums[j]-1)`. We then compare this product with the current `maxProduct` and update `maxProduct` if the current product is larger. After the loops finish iterating through all possible pairs, `maxProduct` will hold the maximum possible value.

```java
class Solution {
    public int maxProduct(int[] nums) {
        int maxProduct = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int currentProduct = (nums[i] - 1) * (nums[j] - 1);
                if (currentProduct > maxProduct) {
                    maxProduct = currentProduct;
                }
            }
        }
        return maxProduct;
    }
}
```
### Algorithm
- Initialize a variable `maxProduct` to 0.
- Use a nested loop to iterate through all pairs of distinct indices `(i, j)`.
- The outer loop runs from `i = 0` to `n-2`.
- The inner loop runs from `j = i + 1` to `n-1`.
- Inside the inner loop, calculate `currentProduct = (nums[i] - 1) * (nums[j] - 1)`.
- Update `maxProduct` by taking the maximum of `maxProduct` and `currentProduct`.
- After the loops complete, return `maxProduct`.

## Sorting the Array
A more efficient approach is to realize that to maximize the product `(a-1)*(b-1)` (where `a` and `b` are positive), we need to choose the largest possible values for `a` and `b`. By sorting the array, we can easily find the two largest elements, which will be at the end of the sorted array.
**Time:** O(n log n), which is dominated by the time taken to sort the array. · **Space:** O(log n) or O(n). The space complexity depends on the implementation of the sorting algorithm. For instance, Java's `Arrays.sort` for primitives uses a variant of Quicksort which requires O(log n) stack space on average.
**Pros:** Much more efficient than the brute-force method, with O(n log n) time complexity.; Easy to implement using built-in sorting functions.
**Cons:** Sorting the entire array is more work than necessary if we only need the two largest elements.; The space complexity might not be O(1) depending on the sorting algorithm used.
### Explanation
The core idea is that the two largest numbers in the array will yield the maximum product. We first sort the input array `nums` in non-decreasing order using a standard sorting algorithm. After sorting, the two largest elements are guaranteed to be located at the last two positions of the array, specifically at indices `n-1` and `n-2`, where `n` is the length of the array. We can then directly access these two elements and compute the required product: `(nums[n-1] - 1) * (nums[n-2] - 1)`. This avoids checking all pairs and significantly reduces the computation time compared to the brute-force method.

```java
import java.util.Arrays;

class Solution {
    public int maxProduct(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return (nums[n - 1] - 1) * (nums[n - 2] - 1);
    }
}
```
### Algorithm
- Sort the input array `nums` in ascending order.
- Let `n` be the length of the array.
- The two largest elements will be at the end of the sorted array: `nums[n-1]` and `nums[n-2]`.
- Calculate and return the product `(nums[n-1] - 1) * (nums[n-2] - 1)`.

## Single Pass to Find Two Largest Elements
The most optimal approach is to find the two largest elements in the array in a single pass. This avoids the overhead of sorting the entire array. We can iterate through the array once, keeping track of the largest and second-largest elements seen so far.
**Time:** O(n), as we iterate through the array only once to find the two largest elements. · **Space:** O(1), as we only use a constant number of extra variables regardless of the input size.
**Pros:** The most efficient solution with a linear time complexity of O(n).; Optimal, as it requires examining each element at least once.; Uses constant extra space.
**Cons:** The logic is slightly more complex than the sorting approach, requiring careful handling of the two largest values.
### Explanation
We can achieve a linear time solution by iterating through the array just once. We maintain two variables, `max1` and `max2`, to store the largest and second-largest numbers found so far. We initialize both to 0, as the problem constraints state `nums[i] >= 1`. We then iterate through each number `num` in the `nums` array. If `num` is greater than `max1`, it means we've found a new largest number. In this case, the old `max1` becomes the new `max2`, and `num` becomes the new `max1`. Otherwise, if `num` is not greater than `max1` but is greater than `max2`, it becomes the new second-largest number, so we update `max2` to `num`. After this single pass, `max1` and `max2` will hold the two largest values in the array, and we can compute the final result as `(max1 - 1) * (max2 - 1)`.

```java
class Solution {
    public int maxProduct(int[] nums) {
        int max1 = 0; // Will hold the largest element
        int max2 = 0; // Will hold the second largest element

        for (int num : nums) {
            if (num > max1) {
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max2 = num;
            }
        }
        return (max1 - 1) * (max2 - 1);
    }
}
```
### Algorithm
- Initialize two variables, `max1` and `max2`, to store the largest and second-largest elements. Initialize them to 0.
- Iterate through each number `num` in the `nums` array.
- If `num` is greater than `max1`:
  - Update `max2` to the old value of `max1`.
  - Update `max1` to `num`.
- Else if `num` is greater than `max2`:
  - Update `max2` to `num`.
- After the loop, `max1` and `max2` will hold the two largest values.
- Return the product `(max1 - 1) * (max2 - 1)`.

# Solutions
### Java

```java
class Solution {
public
  int maxProduct(int[] nums) {
    int ans = 0;
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        ans = Math.max(ans, (nums[i] - 1) * (nums[j] - 1));
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxProduct(vector<int> &nums) {
    int ans = 0;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        ans = max(ans, (nums[i] - 1) * (nums[j] - 1));
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxProduct(self, nums: List[int]) -> int: ans = 0 for i, a in enumerate(nums): for b in nums[i + 1:]: ans = max(ans, (a - 1) * (b - 1)) return ans

```