easy

Maximum Product of Two Elements in an Array

Maximize (a-1) * (b-1) over two distinct array elements.

1. Define the problem

Maximum Product of Two Elements in an Array

Given the array of integers nums, find the two distinct indices i and j such that (numsi - 1) * (numsj - 1) is maximized and return that product. The best product always comes from the two largest values in the array, so find them in a single pass.

Constraints

  • 2 ≤ nums.length ≤ 500
  • 1 ≤ numsi ≤ 103

Example

Inputnums = [3, 4, 5, 2]
Output12

Explanation The two largest values are 5 and 4, giving (5-1) * (4-1) = 4 * 3 = 12.

2. Visualize the solution

Track the two largest values in one pass

Track the two largest values in one pass
Statusinit

value=3. first=3 (was 0), second=0.

What happens in this step

value = nums[0] = 3
3 > first (0)

first becomes 3, second stays 0.
Step 1 of 4

Steps to visualize

  1. Keep two trackers, first and second, for the largest and second-largest values seen.
  2. For each value, if it beats first, shift first down to second and set this as the new first.
  3. Otherwise, if it beats second, update second.
  4. After scanning the whole array, compute (first - 1) * (second - 1).
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Track the two largest values in one pass
Statusinit

value=3. first=3 (was 0), second=0.

What happens in this step

value = nums[0] = 3
3 > first (0)

first becomes 3, second stays 0.
Step 1 of 4
4. Solution

Solution

solution.tsTypeScript
function maxProduct(nums) {
  let first = 0;
  let second = 0;

  for (const value of nums) {
    if (value > first) {
      second = first;
      first = value;
    } else if (value > second) {
      second = value;
    }
  }

  return (first - 1) * (second - 1);
}
Time
O(n)
Space
O(1)
5. Test cases

Test cases

InputExpectedCovers
nums = [3, 4, 5, 2]12example from the docstring
nums = [1, 5]0smallest valid input, one value is the minimum possible
nums = [3, 3, 3]4every value identical
nums = [10, 2]9boundary case, exactly two elements
nums = [1, 2, 3]2ascending values with the top two adjacent
nums = [9, 9, 3, 4]64the two largest values are tied

Keep reading