leetcode - 1464. Maximum Product of Two Elements in an Array

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

Example 1:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: 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
Explanation: 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

Constraints:

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

Solution

Brute Force

Time complexity: $o(n^2)$
Space complexity: $o(1)$

Math Trick

The largest result must be the product of the largest element and second largest element. So go through the list and find out the largest and second largest element.

Time complexity: $o(n)$
Space complexity: $o(1)$

Code

Math Trick

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = 0
        p1, p2 = 0, 0
        for each_num in nums:
            if each_num > p1:
                p2 = p1
                p1 = each_num
            elif each_num > p2:
                p2 = each_num
        return (p1 - 1) * (p2 - 1)