Maximum Product of Two Elements in an Array
EasyPrompt
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^3
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves checking every possible pair of distinct elements in the array. We use nested loops to iterate through all pairs (i, j) where i is not equal to j. For each pair, we calculate the product (nums[i]-1)*(nums[j]-1) and keep track of the maximum product found so far.
Algorithm
- Initialize a variable
maxProductto 0. - Use a nested loop to iterate through all pairs of distinct indices
(i, j). - The outer loop runs from
i = 0ton-2. - The inner loop runs from
j = i + 1ton-1. - Inside the inner loop, calculate
currentProduct = (nums[i] - 1) * (nums[j] - 1). - Update
maxProductby taking the maximum ofmaxProductandcurrentProduct. - After the loops complete, return
maxProduct.
Walkthrough
We initialize a variable maxProduct to 0. The outer loop iterates from the first element to the second-to-last element (index i). The inner loop iterates from the element after i to the last element (index j). This structure ensures that we consider each pair of distinct indices exactly once. Inside the inner loop, we compute the product (nums[i]-1) * (nums[j]-1). We then compare this product with the current maxProduct and update maxProduct if the current product is larger. After the loops finish iterating through all possible pairs, maxProduct will hold the maximum possible value.
class Solution { public int maxProduct(int[] nums) { int maxProduct = 0; int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int currentProduct = (nums[i] - 1) * (nums[j] - 1); if (currentProduct > maxProduct) { maxProduct = currentProduct; } } } return maxProduct; }}Complexity
Time
O(n^2), where n is the number of elements in `nums`. The nested loops result in a quadratic number of comparisons.
Space
O(1), as we only use a constant amount of extra space for variables.
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to find the correct answer as it checks all possibilities.
Cons
Highly inefficient for large arrays due to its O(n^2) time complexity.
Performs a lot of redundant calculations.
A more efficient approach is to realize that to maximize the product (a-1)*(b-1) (where a and b are positive), we need to choose the largest possible values for a and b. By sorting the array, we can easily find the two largest elements, which will be at the end of the sorted array.
Algorithm
- Sort the input array
numsin ascending order. - Let
nbe the length of the array. - The two largest elements will be at the end of the sorted array:
nums[n-1]andnums[n-2]. - Calculate and return the product
(nums[n-1] - 1) * (nums[n-2] - 1).
Walkthrough
The core idea is that the two largest numbers in the array will yield the maximum product. We first sort the input array nums in non-decreasing order using a standard sorting algorithm. After sorting, the two largest elements are guaranteed to be located at the last two positions of the array, specifically at indices n-1 and n-2, where n is the length of the array. We can then directly access these two elements and compute the required product: (nums[n-1] - 1) * (nums[n-2] - 1). This avoids checking all pairs and significantly reduces the computation time compared to the brute-force method.
import java.util.Arrays; class Solution { public int maxProduct(int[] nums) { Arrays.sort(nums); int n = nums.length; return (nums[n - 1] - 1) * (nums[n - 2] - 1); }}Complexity
Time
O(n log n), which is dominated by the time taken to sort the array.
Space
O(log n) or O(n). The space complexity depends on the implementation of the sorting algorithm. For instance, Java's `Arrays.sort` for primitives uses a variant of Quicksort which requires O(log n) stack space on average.
Trade-offs
Pros
Much more efficient than the brute-force method, with O(n log n) time complexity.
Easy to implement using built-in sorting functions.
Cons
Sorting the entire array is more work than necessary if we only need the two largest elements.
The space complexity might not be O(1) depending on the sorting algorithm used.
The most optimal approach is to find the two largest elements in the array in a single pass. This avoids the overhead of sorting the entire array. We can iterate through the array once, keeping track of the largest and second-largest elements seen so far.
Algorithm
- Initialize two variables,
max1andmax2, to store the largest and second-largest elements. Initialize them to 0. - Iterate through each number
numin thenumsarray. - If
numis greater thanmax1:- Update
max2to the old value ofmax1. - Update
max1tonum.
- Update
- Else if
numis greater thanmax2:- Update
max2tonum.
- Update
- After the loop,
max1andmax2will hold the two largest values. - Return the product
(max1 - 1) * (max2 - 1).
Walkthrough
We can achieve a linear time solution by iterating through the array just once. We maintain two variables, max1 and max2, to store the largest and second-largest numbers found so far. We initialize both to 0, as the problem constraints state nums[i] >= 1. We then iterate through each number num in the nums array. If num is greater than max1, it means we've found a new largest number. In this case, the old max1 becomes the new max2, and num becomes the new max1. Otherwise, if num is not greater than max1 but is greater than max2, it becomes the new second-largest number, so we update max2 to num. After this single pass, max1 and max2 will hold the two largest values in the array, and we can compute the final result as (max1 - 1) * (max2 - 1).
class Solution { public int maxProduct(int[] nums) { int max1 = 0; // Will hold the largest element int max2 = 0; // Will hold the second largest element for (int num : nums) { if (num > max1) { max2 = max1; max1 = num; } else if (num > max2) { max2 = num; } } return (max1 - 1) * (max2 - 1); }}Complexity
Time
O(n), as we iterate through the array only once to find the two largest elements.
Space
O(1), as we only use a constant number of extra variables regardless of the input size.
Trade-offs
Pros
The most efficient solution with a linear time complexity of O(n).
Optimal, as it requires examining each element at least once.
Uses constant extra space.
Cons
The logic is slightly more complex than the sorting approach, requiring careful handling of the two largest values.
Solutions
Solution
class Solution {public int maxProduct(int[] nums) { int ans = 0; int n = nums.length; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { ans = Math.max(ans, (nums[i] - 1) * (nums[j] - 1)); } } return ans; }}class Solution {public: int maxProduct(vector<int> &nums) { int ans = 0; int n = nums.size(); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { ans = max(ans, (nums[i] - 1) * (nums[j] - 1)); } } return ans; }};class Solution: def maxProduct(self, nums: List[int]) -> int: ans = 0 for i, a in enumerate(nums): for b in nums[i + 1:]: ans = max(ans, (a - 1) * (b - 1)) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.