LC1464 - 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:

1
2
3

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:

1
2
3

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:

1 2	Input: nums = [3,7] Output: 12

Constraints:

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

Solutions

Sorting

Sort first
then the last two values are the largest two values
find the final answer as required and return

# O(nlogn) time | O(1) space
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        nums.sort()
        return (nums[-1]-1)*(nums[-2]-1)

Two Pointers

This problem is actually to find the first and second largest numbers in the array. We only need to use first and second to represent the subscripts of the first and second largest numbers, and then traverse the array and compare them one by one.

# O(n) time | O(1) space
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        first, second = 0, 1
        if nums[second] > nums[first]:
            first, second = 1, 0
        
        for i in range(2, len(nums)):
            v = nums[i]
            if v > nums[first]:
                first, second = i, first
            elif v > nums[second]:
                second = i
        return (nums[first]-1)*(nums[second]-1)

1.1464. Maximum Product of Two Elements in an Array ↩