Problem

Given an array of both positive and negative integers, return a pair of elements with the highest product.

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.

Example 2:

1
2
3

Input: arr[] = [-1, -3, -4, 2, 0, -5]
Output: [-4, -5]
Explanation: The pair (-4, -5) gives the highest product of 20.

Method 1 - Brute Force

A straightforward solution is to evaluate every pair of elements and keep track of the maximum product. Below is the implementation of this simple solution.

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
28
29
30
31
32
33

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

        int maxProduct = Integer.MIN_VALUE;
        int[] pair = new int[2];

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int product = nums[i] * nums[j];
                if (product > maxProduct) {
                    maxProduct = product;
                    pair[0] = nums[i];
                    pair[1] = nums[j];
                }
            }
        }

        return pair;
    }

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

        int[] nums1 = {1, 4, 3, 6, 7, 0};
        System.out.println("The pair with the highest product is: " + Arrays.toString(solution.maxProductPair(nums1)));  // Output: [6, 7]

        int[] nums2 = {-1, -3, -4, 2, 0, -5};
        System.out.println("The pair with the highest product is: " + Arrays.toString(solution.maxProductPair(nums2)));  // Output: [-4, -5]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def maxProductPair(self, nums):
        if len(nums) < 2:
            return []

        max_product = float('-inf')
        pair = []

        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                product = nums[i] * nums[j]
                if product > max_product:
                    max_product = product
                    pair = [nums[i], nums[j]]

        return pair

# Example usage
solution = Solution()
nums1 = [1, 4, 3, 6, 7, 0]
print(f"The pair with the highest product is: {solution.maxProductPair(nums1)}")  # Output: [6, 7]

nums2 = [-1, -3, -4, 2, 0, -5]
print(f"The pair with the highest product is: {solution.maxProductPair(nums2)}")  # Output: [-4, -5]

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Use sorting

A more efficient solution involves sorting. The steps are:

  1. Sort the input array in ascending order.
  2. If all elements are positive, return the product of the last two elements.
  3. Otherwise, return the maximum of the products of the first two and the last two elements.

This solution has a time complexity of O(n log n).

Code

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

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

        Arrays.sort(nums);  // Sort the array in ascending order
        int product1 = nums[0] * nums[1];  // Product of the first two elements
        int product2 = nums[nums.length - 1] * nums[nums.length - 2];  // Product of the last two elements

        if (product1 > product2) {
            return new int[] {nums[0], nums[1]};
        } else {
            return new int[] {nums[nums.length - 2], nums[nums.length - 1]};
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def maxProductPair(self, nums):
        if len(nums) < 2:
            return []

        nums.sort()  # Sort the array in ascending order
        product1 = nums[0] * nums[1]  # Product of the first two elements
        product2 = nums[-1] * nums[-2]  # Product of the last two elements

        if product1 > product2:
            return [nums[0], nums[1]]
        else:
            return [nums[-2], nums[-1]]

Method 3 - Using Second Max and Second Min element

An efficient solution can address the problem in a single traversal of the input array. The idea is to track the following four values during the traversal:

  1. The largest positive value.
  2. The second largest positive value.
  3. The smallest (most negative) value.
  4. The second smallest (most negative) value. At the end of the traversal, compare the products of the two positive values and the two negative values and return the higher product. Below is the implementation of this idea.

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
28
29
30
31
32
33
34
35
36
37

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

        // Initialize variables to track the required values
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE;
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;

        for (int num : nums) {
            // Update the largest and second largest positive values
            if (num > max1) {
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max2 = num;
            }

            // Update the smallest and second smallest negative values
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }

        // Compare products and return the pair with the highest product
        if (max1 * max2 > min1 * min2) {
            return new int[] {max1, max2};
        } else {
            return new int[] {min1, min2};
        }
    }

}
 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
28
29

class Solution:
    def maxProductPair(self, nums):
        if len(nums) < 2:
            return []

        # Initialize variables to track the required values
        max1 = max2 = float('-inf')
        min1 = min2 = float('inf')

        for num in nums:
            # Update the largest and second largest positive values
            if num > max1:
                max2 = max1
                max1 = num
            elif num > max2:
                max2 = num

            # Update the smallest and second smallest negative values
            if num < min1:
                min2 = min1
                min1 = num
            elif num < min2:
                min2 = num

        # Compare products and return the pair with the highest product
        if max1 * max2 > min1 * min2:
            return [max1, max2]
        else:
            return [min1, min2]

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)