Problem

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).

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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:

1
2
3
4

Input:
nums = [3,7]
Output:
 12

Constraints

  • 2 <= nums.length <= 500
  • 1 <= nums[i] <= 10^3

Solution

Method 1 – Track Two Maximums

Intuition

To maximize (nums[i] - 1) * (nums[j] - 1), we want the two largest numbers in the array. Subtract 1 from each and multiply. Since all numbers are positive, we only need to track the two largest elements.

If negative numbers were allowed: If the array could contain negative numbers, the maximum product could also come from the two smallest (most negative) numbers, since their product is positive. In that case, we would need to track both the two largest and two smallest numbers, and return the maximum of (max1-1)(max2-1) and (min1-1)(min2-1).

Approach

  1. Initialize two variables, max1 and max2, to track the largest and second largest numbers.
  2. Iterate through the array:
    • If the current number is greater than max1, update max2 to max1 and max1 to the current number.
    • Else if the current number is greater than max2, update max2.
  3. Return (max1 - 1) * (max2 - 1).

Note: If negative numbers were allowed, we would also need to consider the two smallest numbers, but for this problem, all numbers are positive.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
	int maxProduct(vector<int>& nums) {
		int max1 = 0, max2 = 0;
		for (int num : nums) {
			if (num > max1) {
				max2 = max1;
				max1 = num;
			} else if (num > max2) {
				max2 = num;
			}
		}
		return (max1 - 1) * (max2 - 1);
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
	public int maxProduct(int[] nums) {
		int max1 = 0, max2 = 0;
		for (int num : nums) {
			if (num > max1) {
				max2 = max1;
				max1 = num;
			} else if (num > max2) {
				max2 = num;
			}
		}
		return (max1 - 1) * (max2 - 1);
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
	def maxProduct(self, nums: list[int]) -> int:
		max1 = max2 = 0
		for num in nums:
			if num > max1:
				max2 = max1
				max1 = num
			elif num > max2:
				max2 = num
		return (max1 - 1) * (max2 - 1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func maxProduct(nums []int) int {
	max1, max2 := 0, 0
	for _, num := range nums {
		if num > max1 {
			max2 = max1
			max1 = num
		} else if num > max2 {
			max2 = num
		}
	}
	return (max1 - 1) * (max2 - 1)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

function maxProduct(nums: number[]): number {
	let max1 = 0, max2 = 0;
	for (const num of nums) {
		if (num > max1) {
			max2 = max1;
			max1 = num;
		} else if (num > max2) {
			max2 = num;
		}
	}
	return (max1 - 1) * (max2 - 1);
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. We scan the array once.
  • 🧺 Space complexity: O(1), only a few variables are used.