Maximum Product of Two Elements in an Array

Problem Description

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).

Key Insights

• The problem requires selecting two distinct elements from the array and multiplying their decremented values.
• The maximum product is obtained by using the two largest numbers in the array, as larger numbers will yield a higher product after decrementing.
• Sorting the array or finding the two maximum values directly are viable approaches to solve the problem efficiently.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use a simple approach by iterating through the array to find the two largest numbers. We then compute the product of their decremented values. This approach ensures that we only traverse the array once, leading to a time complexity of O(n).

The algorithm can be summarized in the following steps:

1. Initialize two variables to store the maximum and second maximum values.
2. Iterate through the array and update these variables accordingly.
3. Calculate the result using the formula (max1 - 1) * (max2 - 1).

Code Solutions