Maximum Product of Two Elements in an Array

Difficulty: Easy | Acceptance: 83.60% | Paid: No Topics: Array, Sorting, Heap (Priority Queue)

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

• Examples
• Constraints
• Brute Force
• Sorting
• Heap (Priority Queue)
• Single Pass

Examples

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.

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.

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

Constraints

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

Brute Force

Intuition Check every possible pair of elements in the array to find the maximum product.

Steps

• Initialize a variable maxProd to store the maximum product found.
• Iterate through the array with two nested loops.
• For each pair (i, j) where i < j, calculate (nums[i] - 1) * (nums[j] - 1).
• Update maxProd if the current product is greater.
• Return maxProd.

from typing import List

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

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple but inefficient for large arrays.

Sorting

Intuition The maximum product will be formed by the two largest numbers in the array. Sorting allows us to easily access these two numbers.

Steps

• Sort the array in ascending order.
• The two largest numbers will be at the end of the array.
• Calculate the product using the last two elements.

from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        nums.sort()
        return (nums[-1] - 1) * (nums[-2] - 1)

Complexity

• Time: O(n log n)
• Space: O(1) or O(n) depending on the sorting algorithm.
• Notes: More efficient than brute force, but sorting is not strictly necessary.

Heap (Priority Queue)

Intuition We can use a Max-Heap to efficiently retrieve the two largest elements in the array.

Steps

• Insert all elements into a Max-Heap.
• Extract the largest element (root).
• Extract the second largest element (new root).
• Calculate the product.

import heapq
from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # Python's heapq is a min-heap, so we invert values to simulate a max-heap
        max_heap = [-x for x in nums]
        heapq.heapify(max_heap)
        
        first = -heapq.heappop(max_heap)
        second = -heapq.heappop(max_heap)
        
        return (first - 1) * (second - 1)

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Useful if we need to dynamically access top K elements, but overkill for just two.

Single Pass

Intuition We only need the two largest numbers. We can find them in a single traversal without sorting or a heap.

Steps

• Initialize two variables, max1 and max2, to keep track of the largest and second largest numbers found so far.
• Iterate through the array.
• If the current number is greater than max1, update max2 to be max1, and max1 to be the current number.
• Else if the current number is greater than max2, update max2 to be the current number.
• Return the product (max1 - 1) * (max2 - 1).

from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max1 = max2 = 0
        for num in nums:
            if num > max1:
                max2 = max1
                max1 = num
            elif num > max2:
                max2 = num
        return (max1 - 1) * (max2 - 1)

Complexity

• Time: O(n)
• Space: O(1)
• Notes: The most optimal approach for this problem.