Problem

Find the maximum product of two distinct numbers in a sequence of non-negative integers.

Examples

Example 1:

1
2
3

Input: nums = [1, 4, 3, 6, 7, 0]
Output: [6, 7]
Explanation: The pair (6, 7) gives the highest product of 42.

Solution

Method 1 - Use max and second maximum

We have already seen the problem with both positive and negative integers - Maximum Pairwise Product 2 - Find pair with maximum product in array of Integers. Just use Maximum Pairwise Product 2 - Find pair with maximum product in array of Integers#Method 3 - Using Second Max and Second Min element, and just just use first and second max to find the answer.

So, the approach is:

  1. Traverse the array to identify the two largest distinct values.
  2. Return the product of these two values.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }

        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE;

        for (int num : nums) {
            if (num > max1) {
                max2 = max1;
                max1 = num;
            } else if (num > max2 && num != max1) {
                max2 = num;
            }
        }

        return max1 * max2;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] nums1 = {1, 4, 3, 6, 7, 0};
        System.out.println("The maximum product of two distinct numbers is: " + solution.maxProduct(nums1));  // Output: 42
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def maxProduct(self, nums):
        if len(nums) < 2:
            return 0
        
        max1 = max2 = float('-inf')
        
        for num in nums:
            if num > max1:
                max2 = max1
                max1 = num
            elif num > max2 and num != max1:
                max2 = num
        
        return max1 * max2

# Example usage
solution = Solution()
nums1 = [1, 4, 3, 6, 7, 0]
print(f"The maximum product of two distinct numbers is: {solution.maxProduct(nums1)}")  # Output: 42

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the input array because we traverse the array a constant number of times.
  • 🧺 Space complexity: O(1), as we are using a constant amount of extra space regardless of the input size.