#1464

Easy

LeetCode Problem Workspace

Maximum Product of Two Elements in an Array

Find the maximum product of two elements in an array by carefully selecting indices and leveraging sorting for efficiency.

array sorting heap priority queue

Problem Statement

Given an integer array nums, find two distinct indices i and j such that the product (nums[i]-1)*(nums[j]-1) is maximized. Return the maximum product value.

Constraints: nums.length is at least 2 and at most 500, and each element nums[i] is between 1 and 1000. Examples: nums = [3,4,5,2] yields 12, nums = [1,5,4,5] yields 16, nums = [3,7] yields 12.

Examples

Example 1

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

Output: 12

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

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

Example details omitted.

Constraints

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

Solution Approach

Brute Force

Iterate over all pairs of indices i and j using two nested loops, computing (nums[i]-1)*(nums[j]-1) for each. Track the maximum product seen. This method is simple but inefficient for larger arrays.

Sort-Based Optimization

Sort nums in ascending order, then compute the product of the last two elements minus one each. This leverages the pattern of largest elements producing the maximum product and simplifies implementation to a single calculation.

Linear Scan for Top Two Elements

Maintain two variables max1 and max2 while iterating through nums once. Update them whenever a larger number is found. Return (max1-1)*(max2-1). This avoids sorting and achieves O(n) time and O(1) space.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Brute force has O(n^2) time, while sorting gives O(n log n). The linear scan method achieves O(n) time with O(1) space. All approaches require constant extra memory aside from the input array.

What Interviewers Usually Probe

Look for top elements quickly instead of testing every pair.
Expect discussion of both sorting and linear scan methods.
Clarify array constraints to justify linear-time optimization.

Common Pitfalls or Variants

Common pitfalls

Forgetting to subtract 1 from each number before multiplying.
Assuming elements can repeat without checking distinct indices.
Using nested loops unnecessarily when a linear scan suffices.

Follow-up variants

Find the maximum product of k elements in an array.
Compute the maximum product modulo a large prime.
Find the pair with the maximum product where elements must be consecutive.

FAQ

What is the best way to find the maximum product of two elements in an array?

Use a single linear pass to track the top two numbers or sort the array and take the last two elements; both ensure you maximize (nums[i]-1)*(nums[j]-1).

Can duplicate values affect the maximum product?

Yes, duplicates are valid if they appear at different indices. Always consider distinct positions when computing the product.

Is sorting necessary to solve this problem?

No, a linear scan for the top two numbers achieves the same result in O(n) time without extra sorting overhead.

What common mistakes should I avoid?

Remember to subtract 1 from each number before multiplying, and don't ignore array constraints that allow only valid indices.

How does the array plus sorting pattern apply here?

This pattern helps identify the largest elements efficiently, guiding toward a solution that maximizes the product without checking all pairs.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

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

Solution 2

#### Python3

1

2

3

4

5

6

7

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

Solution 3

#### Python3

1

2

3

4

5

6

7

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

Continue Practicing

#1424 diagonal traverse ii #1383 maximum performance of a team #1353 maximum number of events that can be attended