We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Product of Two Elements in an Array

Number: 1574

Difficulty: Easy

Paid? No

Companies: Amazon, Google, Cisco, Apple, Samsung

Problem Description

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

Key Insights

  • Only the two largest numbers in the array are needed to compute the maximum product.
  • Sorting or a single pass can be used to identify the top two maximum elements.
  • The formula subtracts 1 from each selected number, so even if the array has duplicates, the two largest values provide the answer.

Space and Time Complexity

Time Complexity: O(n) – scanning the array one time to find the two largest elements.
Space Complexity: O(1) – only constant extra space is used.

Solution

The solution involves iterating through the array once while keeping track of the two largest numbers encountered. After identifying these two numbers, we calculate the result using (max1-1) * (max2-1). This approach avoids the overhead of sorting and directly provides the answer in linear time. Edge cases such as small-sized input arrays are handled by the problem constraints ensuring there are always at least two elements.

Code Solutions

# Python Solution

def maxProduct(nums):
    # Initialize the two maximum numbers as negative (since nums[i] >= 1 by constraint)
    max1, max2 = 0, 0
    
    # Iterate over each number in the array
    for num in nums:
        # If current number is greater than max1, update max1 and max2 accordingly
        if num > max1:
            max2 = max1   # previous maximum becomes second maximum
            max1 = num    # update the maximum
        # If current number is not greater than max1 but greater than max2, update max2
        elif num > max2:
            max2 = num
    # Compute the desired product from the two largest numbers after subtracting one from each
    return (max1 - 1) * (max2 - 1)

# Example usage:
if __name__ == "__main__":
    print(maxProduct([3, 4, 5, 2]))  # Output: 12
← Back to All Questions