Problem

Given an integer array nums, find three numbers whose product is maximum and return the maximum product.

Examples

Example 1:

1
2

Input: nums = [1,2,3]
Output: 6

Example 2:

1
2

Input: nums = [1,2,3,4]
Output: 24

Example 3:

1
2

Input: nums = [-1,-2,-3]
Output: -6

Solution

Method 1 - Sorting

Sort the given array in ascending order and you have to take the maximum of these cases to get the answer..

  1. product of last 3 numbers in sorted array
  2. Product of first two and last number in the sorted array

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {

	public int maximumProduct(int[] nums) {
		Arrays.sort(nums);
		//One of the Three Numbers is the maximum value in the array.
		int n = nums.length;
		int a = nums[n - 1] * nums[n - 2] * nums[n - 3];
		int b = nums[0] * nums[1] * nums[n - 1];
		return a > b ? a : b;
	}
}

Complexity

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

Method 2 - Find 3 max and min numbers using maxHeap

Think of the case like: [-100,-98,-1,2,3,4]

Code

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

class Solution {

	public int maximumProduct(int[] nums) {
		PriorityQueue<Integer> minHeap = new PriorityQueue<>();
		PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

		for (int num: nums) {
			minHeap.add(num);
			maxHeap.add(num);
		}
		
		int min1 = minHeap.poll(), min2 = minHeap.poll(), min3 = minHeap.poll();
		int max1 = maxHeap.poll(), max2 = maxHeap.poll(), max3 = maxHeap.poll();
		
		return Math.max(min1 * min2 * max1, max1 * max2 * max3);
		
	}
}

Complexity

  • ⏰ Time complexity: O(n) - O(n + log n). In a normal heap, adding n elements take O(n) time, and finding 3 max elements take 3 log n time.
  • 🧺 Space complexity: O(n)

Method 3 - Finding 3 max numbers

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

class Solution {

	public int maximumProduct(int[] nums) {
		int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
		int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE, min3 = Integer.MAX_VALUE;
		for(int i = 0; i < nums.length; i++){
			if(nums[i] <= min1){
				min2 = min1;
				min1 = nums[i];
			} 
			else if(nums[i] <= min2){
				min2 = nums[i];
			}
			if(nums[i] >= max1){ 
				max3 = max2;
				max2 = max1;
				max1 = nums[i];
			} 
			else if(nums[i] >= max2){
				max3 = max2;
				max2 = nums[i];
			} 
			else if(nums[i] >= max3){
				max3 = nums[i];
			}
		}
		return Math.max(min1 * min2 * max1, max1 * max2 * max3);
		
	}
}

Complexity

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