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 <= 5001 <= nums[i] <= 10^3One effective way to find the maximum product is by first sorting the array, then selecting the two largest elements, which will naturally be at the end of the sorted list. The product of their decremented values will provide the result.
The C implementation sorts the array using a simple bubble sort. Once sorted, the two largest elements are accessed directly using their indices at the end of the array. After computing the product of their decremented values, the result is returned.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) due to the bubble sort implementation. Space Complexity: O(1) since no extra space is used.
This approach finds the two largest numbers in a single pass without sorting. By iterating over the array, we track the largest and second-largest numbers. With these two numbers, we compute the maximum product efficiently.
The C implementation maintains two variables to track the largest and second-largest numbers encountered. Each element is compared in sequence, and the variables are adjusted appropriately to find these numbers without sorting the full array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) because we pass through the array just once. Space Complexity: O(1) as no additional space is required.
| Approach | Complexity |
|---|---|
| Approach 1: Sorting Maximum Two Elements | Time Complexity: O(n^2) due to the bubble sort implementation. Space Complexity: O(1) since no extra space is used. |
| Approach 2: Single Pass for Maximum Two Elements | Time Complexity: O(n) because we pass through the array just once. Space Complexity: O(1) as no additional space is required. |
Maximum Product Subarray - Dynamic Programming - Leetcode 152 • NeetCode • 452,961 views views
Watch 9 more video solutions →Practice Maximum Product of Two Elements in an Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor