Problem Description

The Leetcode problem Maximum Product of Two Elements in an Array asks you to find the maximum value of (nums[i] - 1) * (nums[j] - 1) where nums is a given array of integers, and i and j are two different indices (i.e., i != j).

Constraints:

• You must select two distinct elements from the array.
• Each element can only be used once in the calculation.
• The input array will always contain at least two elements.
• The solution should be efficient and handle large arrays.

Thought Process

The naive approach is to try all possible pairs in the array, calculate (nums[i] - 1) * (nums[j] - 1) for each, and keep track of the maximum result. However, this brute-force method is inefficient for large arrays, as it checks every possible pair.

By examining the formula, notice that the product will be maximized when both nums[i] and nums[j] are as large as possible. Thus, instead of checking every pair, we can focus on finding the two largest values in the array. Subtracting 1 from both and multiplying will always give the highest result.

This insight allows us to optimize the solution by avoiding unnecessary computations.

Solution Approach

• Step 1: Traverse the array once to find the largest number (max1).
• Step 2: Traverse the array again (or during the same traversal) to find the second largest number (max2), making sure it's at a different index than max1.
• Step 3: Compute the product (max1 - 1) * (max2 - 1) and return it.

This approach only requires a single pass through the array (by keeping track of the two largest values as you go), making it very efficient. No extra data structures are needed, and the logic is easy to follow.

Example Walkthrough

Input: nums = [3, 4, 5, 2]
Process:

• Start: max1 = -infinity, max2 = -infinity
• First number (3): max1 = 3, max2 = -infinity
• Second number (4): max1 = 4, max2 = 3
• Third number (5): max1 = 5, max2 = 4
• Fourth number (2): No change (both max1 and max2 are larger)

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n^2) because you check all pairs.
  • Space Complexity: O(1) (no extra space needed).
• Optimized approach:
  • Time Complexity: O(n) since you only need a single pass through the array to find the two largest numbers.
  • Space Complexity: O(1) because you only store two variables.

The optimized solution is significantly faster and uses minimal memory.

Summary

This problem demonstrates the importance of understanding the mathematical structure of a problem. By realizing that the maximum product is always achieved by the two largest numbers, we can avoid brute-force and solve the problem efficiently in linear time. The solution is both elegant and practical, requiring only a single traversal and constant space.

Code Implementation

class Solution:
    def maxProduct(self, nums):
        max1 = max2 = 0
        for n in nums:
            if n > max1:
                max2 = max1
                max1 = n
            elif n > max2:
                max2 = n
        return (max1 - 1) * (max2 - 1)
      

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int max1 = 0, max2 = 0;
        for (int n : nums) {
            if (n > max1) {
                max2 = max1;
                max1 = n;
            } else if (n > max2) {
                max2 = n;
            }
        }
        return (max1 - 1) * (max2 - 1);
    }
};
      

class Solution {
    public int maxProduct(int[] nums) {
        int max1 = 0, max2 = 0;
        for (int n : nums) {
            if (n > max1) {
                max2 = max1;
                max1 = n;
            } else if (n > max2) {
                max2 = n;
            }
        }
        return (max1 - 1) * (max2 - 1);
    }
}
      

var maxProduct = function(nums) {
    let max1 = 0, max2 = 0;
    for (let n of nums) {
        if (n > max1) {
            max2 = max1;
            max1 = n;
        } else if (n > max2) {
            max2 = n;
        }
    }
    return (max1 - 1) * (max2 - 1);
};