Formatted question description: https://leetcode.ca/all/1464.html
1464. Maximum Product of Two Elements in an Array (Easy)
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)
.
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 <= 500
1 <= nums[i] <= 10^3
Related Topics:
Array
Solution 1. Brute Force
// OJ: https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
int maxProduct(vector<int>& nums) {
int N = nums.size(), ans = 0;
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;
}
};
Solution 2. Heap
We just need find the greatest two elements.
// OJ: https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int maxProduct(vector<int>& nums) {
make_heap(begin(nums), end(nums));
pop_heap(begin(nums), end(nums));
pop_heap(begin(nums), end(nums) - 1);
return (nums.back() - 1) * (*(nums.end() - 2) - 1);
}
};
Solution 3. Two pass
// OJ: https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int maxProduct(vector<int>& nums) {
auto it = max_element(begin(nums), end(nums));
swap(*it, nums[0]);
it = max_element(begin(nums) + 1, end(nums));
return (nums[0] - 1) * (*it - 1);
}
};
Solution 4. One pass
// OJ: https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int maxProduct(vector<int>& nums) {
int a = 0, b = 0;
for (int n : nums) {
if (n >= a) {
b = a;
a = n;
} else if (n > b) b = n;
}
return (a - 1) * (b - 1);
}
};
Java
class Solution {
public int maxProduct(int[] nums) {
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE;
for (int num : nums) {
if (num > max1) {
max2 = max1;
max1 = num;
} else if (num > max2)
max2 = num;
}
return (max1 - 1) * (max2 - 1);
}
}