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] <= 103
My Solution
We can solve this problem by iterating through the array and keeping track of the two largest integers. Afterward, we just subtract 1 from both numbers and multiply them together and return the result.
Time complexity is O(n) because we iterate through the array once. Space complexity is O(1) since we only require constant extra space.
class Solution {
public int maxProduct(int[] nums) {
int num1 = 0;
int num2 = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
if (nums[i] > num1) {
num2 = num1;
num1 = nums[i];
}
else if (nums[i] > num2) {
num2 = nums[i];
}
}
num1--;
num2--;
return (num1 * num2);
}
}