Problem Description

You are given an array of integers called nums. Your task is to select two different indices i and j from this array and calculate the product (nums[i]-1) * (nums[j]-1). You need to find and return the maximum possible value of this product.

In other words, you need to:

1. Pick any two different elements from the array
2. Subtract 1 from each of these elements
3. Multiply the results together
4. Find the combination that gives you the largest product

For example, if you have an array [3, 4, 5, 2], you could choose:

• Elements 3 and 4: (3-1) * (4-1) = 2 * 3 = 6
• Elements 3 and 5: (3-1) * (5-1) = 2 * 4 = 8
• Elements 3 and 2: (3-1) * (2-1) = 2 * 1 = 2
• Elements 4 and 5: (4-1) * (5-1) = 3 * 4 = 12
• Elements 4 and 2: (4-1) * (2-1) = 3 * 1 = 3
• Elements 5 and 2: (5-1) * (2-1) = 4 * 1 = 4

The maximum product would be 12, which comes from choosing elements 4 and 5.

Intuition

To maximize the product (nums[i]-1) * (nums[j]-1), we need to think about what makes a product large. Since we're multiplying two values together, we want both values to be as large as possible.

After subtracting 1 from each element, the largest possible values come from the largest elements in the original array. For instance, if we have elements 10 and 8 in the array, after subtracting 1, we get 9 and 7, which when multiplied give us 63. This would be much larger than using smaller elements like 3 and 4, which would give us (3-1) * (4-1) = 2 * 3 = 6.

The key insight is that to maximize (a-1) * (b-1), we should choose the two largest elements in the array. This is because:

• Larger numbers remain large even after subtracting 1
• The product of two large numbers is maximized when both numbers are as large as possible

However, the given solution takes a brute force approach by checking all possible pairs. It iterates through every combination of two different elements, calculates (nums[i]-1) * (nums[j]-1) for each pair, and keeps track of the maximum value found. While this guarantees finding the correct answer, it's not the most efficient approach.

A more optimal solution would be to simply find the two largest elements in the array and calculate their product after subtracting 1 from each. This would reduce the time complexity from O(n²) to O(n).

Learn more about Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation uses a brute force approach with nested loops to examine all possible pairs of elements in the array.

Algorithm Steps:

1. Initialize a variable ans to 0 to keep track of the maximum product found so far.

2. Use enumerate() to iterate through the array with both index i and value a:

   • The outer loop picks the first element of each pair

3. For each element a at position i, iterate through all elements that come after it using nums[i + 1:]:

   • This ensures we only check each pair once and don't compare an element with itself
   • The slice nums[i + 1:] gives us all elements from position i+1 to the end of the array

4. For each pair (a, b), calculate the product (a - 1) * (b - 1)

5. Update ans using max(ans, (a - 1) * (b - 1)) to keep the maximum value seen so far

6. After checking all pairs, return the maximum product stored in ans

Example Walkthrough:

For nums = [3, 4, 5, 2]:

• When i=0, a=3: Check pairs with [4, 5, 2]
  • (3-1) * (4-1) = 6
  • (3-1) * (5-1) = 8
  • (3-1) * (2-1) = 2
• When i=1, a=4: Check pairs with [5, 2]
  • (4-1) * (5-1) = 12
  • (4-1) * (2-1) = 3
• When i=2, a=5: Check pairs with [2]
  • (5-1) * (2-1) = 4
• Maximum found: 12

Time Complexity: O(n²) where n is the length of the array, as we check all possible pairs.

Space Complexity: O(1) as we only use a constant amount of extra space for the ans variable.

Example Walkthrough

Let's walk through the solution with a small example: nums = [2, 5, 3, 7]

Step 1: Initialize

• Set ans = 0 to track the maximum product

Step 2: First iteration (i=0, a=2)

• Check element 2 against all elements after it: [5, 3, 7]
• Pair (2, 5): (2-1) * (5-1) = 1 * 4 = 4
  • Update: ans = max(0, 4) = 4
• Pair (2, 3): (2-1) * (3-1) = 1 * 2 = 2
  • Update: ans = max(4, 2) = 4
• Pair (2, 7): (2-1) * (7-1) = 1 * 6 = 6
  • Update: ans = max(4, 6) = 6

Step 3: Second iteration (i=1, a=5)

• Check element 5 against all elements after it: [3, 7]
• Pair (5, 3): (5-1) * (3-1) = 4 * 2 = 8
  • Update: ans = max(6, 8) = 8
• Pair (5, 7): (5-1) * (7-1) = 4 * 6 = 24
  • Update: ans = max(8, 24) = 24

Step 4: Third iteration (i=2, a=3)

• Check element 3 against all elements after it: [7]
• Pair (3, 7): (3-1) * (7-1) = 2 * 6 = 12
  • Update: ans = max(24, 12) = 24

Step 5: Return result

• All pairs have been checked
• Return ans = 24

The maximum product is 24, achieved by selecting the two largest elements (5 and 7) from the array.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The code uses two nested loops to iterate through all pairs of elements in the array. The outer loop runs n times (where n is the length of the array), and for each iteration i, the inner loop runs (n - i - 1) times. This gives us a total of:

• (n-1) + (n-2) + ... + 1 = n(n-1)/2 iterations

Therefore, the time complexity is O(n²).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• Variable ans to store the maximum product
• Loop variables i, a, and b

No additional data structures are created that scale with the input size, so the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient O(n²) Solution When O(n) is Possible

The brute force approach checks all possible pairs, resulting in O(n²) time complexity. However, this problem can be solved in O(n) time by recognizing that to maximize (a-1) * (b-1), we simply need to find the two largest numbers in the array.

Why this works: Since we're subtracting 1 from both numbers before multiplying, the product is maximized when both (a-1) and (b-1) are as large as possible, which happens when a and b are the two largest values in the array.

Optimized O(n) Solution:

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # Find the two largest numbers in a single pass
        first_max = second_max = 0
      
        for num in nums:
            if num > first_max:
                second_max = first_max
                first_max = num
            elif num > second_max:
                second_max = num
      
        return (first_max - 1) * (second_max - 1)

2. Not Handling Edge Cases with Negative Numbers

If the problem allowed negative numbers in the array, the current approach might miss the optimal solution. For example, with [-5, -4, 3, 2], the maximum product would be (-5-1) * (-4-1) = (-6) * (-5) = 30, not (3-1) * (2-1) = 2.

Solution: If negative numbers are possible, you'd need to track both the two largest and two smallest values:

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # Track both largest and smallest values
        nums.sort()
        # Compare product of two smallest vs two largest
        return max(
            (nums[0] - 1) * (nums[1] - 1),  # Two smallest (could be negative)
            (nums[-1] - 1) * (nums[-2] - 1)  # Two largest
        )

3. Unnecessary Memory Usage with Slicing

The current solution uses nums[i + 1:] which creates a new list slice for each iteration. While this doesn't affect the overall space complexity (still O(1)), it creates unnecessary temporary objects.

Better approach using indices:

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max_product = 0
        n = len(nums)
      
        for i in range(n):
            for j in range(i + 1, n):
                current_product = (nums[i] - 1) * (nums[j] - 1)
                max_product = max(max_product, current_product)
      
        return max_product