Maximum Product Of Two Elements In An Array - Leetcode Solution

Problem Statement: Given an integer array nums, find the maximum product of two distinct elements in it.

Example 1:

Input: nums = [3,4,5,2] Output: 20 Explanation: The maximum product is 5 * 4 = 20. Example 2:

Input: nums = [1,5,4,5] Output: 25 Explanation: The maximum product is 5 * 5 = 25. Example 3:

Input: nums = [3,7] Output: 21 Explanation: The maximum product is 3 * 7 = 21.

Solution: This problem can be solved using a simple approach. We need to find the maximum element and the second maximum element in the given array and then multiply them to get the maximum product.

Step 1: Initialize two variables max1 and max2 to -infinity (-∞). Step 2: Traverse the array nums using a loop. For each element in nums, do the following. Step 3: If the element is greater than the current value of max1, then update max2 with the current value of max1 and update max1 with the current element. Step 4: If the element is between max1 and max2, then update only max2 with the current element. Step 5: After the loop, return the result of max1 * max2.

Code:

def maxProduct(nums: List[int]) -> int: max1 = max2 = -float("inf") for num in nums: if num > max1: max2 = max1 max1 = num elif num > max2: max2 = num return (max1 - 1) * (max2 - 1)

Time Complexity: O(n) Space Complexity: O(1)

Explanation: In the above code, we have defined a function maxProduct which takes an integer array nums as input and returns an integer as output.

We have initialized two variables max1 and max2 to -infinity (-∞) using max1 = max2 = -float("inf") because we want to make sure that the first element of the array is greater than both max1 and max2.

Then, we have traversed the array nums using a for loop. For each element in nums, we are checking whether it is greater than max1 or max2 or not.

If it is greater than max1, then we will update max2 with the current value of max1 and update max1 with the current element because the current element is greater than both max1 and max2.

If it is between max1 and max2, then we will update only max2 with the current element because the current element is greater than max2 but less than max1.

After the loop, we will return the result of max1 * max2 which gives us the maximum product of two distinct elements.

Overall, the time complexity of this solution is O(n) because we are traversing the array only once and the space complexity is O(1) because we are using only two variables max1 and max2.

1