The first solution for this problem will come to your mind will be sort the array in ascending/ descending order and multiply the largest 3 numbers. But wait here the twist comes in this problem. Does your function work with negative numbers?
If your input array is [-10,-10,5,3,2] then the largest product of 3 is (-10*-10*3) not (2*3*5).
To brute force ? an answer we could iterate through arrayOfInts and multiply each integer by each other integer, and then multiply that product by each other other integer. This would probably involve nesting 3 loops. But that would be an O(n3)O(n^3)O(n?3??) runtime! We can definitely do better than that.
Sorting the array can still be used to solve the problem. If we sort the input array of positive/negative integers in ascending order then either of the following will give us highest product of 3.
int highestProductOf3 = Math.max(arr[0]*arr[1]*arr[arr.length-1] , arr[arr.length-1]*arr[arr.length-2]*arr[arr.length-3]);
Consider the following diagram
But Sorting takes O(nlgn)O(n\lg{n})O(nlgn) time. That's better than the O(n3)O(n^3)O(n?3??) time our brute force approach required, but we can still do better.
A better approach is to use a greedy algorithm. How can we keep track of the highestProductOf3 while walking through the array? In other words for each new current number during our iteration, how do we know if it gives us a new highestProductOf3?
We have a new highestProductOf3 if the current number multiplied by two other numbers gives us a product that's higher than our current highestProductOf3. To do the same what must we keep track while walking through the array.Our first guess might be:
1. Current highestProductOf3.
2. The three numbers which gives us the highestProductOf3.
But consider the following example:
int[] arr = new int[]{2, 10, -5, 6, -100};
Right before we hit -100, our highestProductOf3 was 120, and the three numbers which gives us the highestProductOf3 were [2,10,6]. But once we hit -100, suddenly we can take -100*-5*10 to get 5000. So we should have "held on to" that -5, even though it wasn't one of the three numbers which gives us the highestProductOf3.
We need something a little more information to get the highest product of 3 from an integer array. As we have already noticed from the sorting array solution that there are only 2 possibility to get the highestProductOf3.
1. Product of Maximum, second maximum and third maximum element.
2. Product of Minimum and second minimum and the maximum element in the array. When the Minimum and second minimum are negative numbers.
So the algorithm used here to solve the problem is
1. Scan the array and keep track of Maximum, second maximum and third maximum element present in the array.
2. Scan the array and keep track of Minimum and second minimum element present in the array.
3. Return the maximum of product of Maximum, second maximum and third maximum and product of Minimum, second minimum and Maximum element.
The Java implementation is :
package com.tuturself.pc; public class HighestProductOf3 { /* * Function to find a maximum product of a triplet in array of integers */ public static int maxProduct(int arr[], int n) { // if size is less than 3, no triplet exists if (n < 3) return -1; // Initialize Maximum, second maximum and third // maximum element int maximum = Integer.MIN_VALUE, secondMaximum = Integer.MIN_VALUE, thirdMaximum = Integer.MIN_VALUE; // Initialize Minimum and second mimimum element int minimum = Integer.MAX_VALUE, secondMinimum = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { // Update Maximum, second maximum and third // maximum element if (arr[i] > maximum) { thirdMaximum = secondMaximum; secondMaximum = maximum; maximum = arr[i]; } // Update second maximum and third maximum element else if (arr[i] > secondMaximum) { thirdMaximum = secondMaximum; secondMaximum = arr[i]; } // Update third maximum element else if (arr[i] > thirdMaximum) thirdMaximum = arr[i]; // Update Minimum and second mimimum element if (arr[i] < minimum) { secondMinimum = minimum; minimum = arr[i]; } // Update second mimimum element else if (arr[i] < secondMinimum) secondMinimum = arr[i]; } return Math.max(minimum * secondMinimum * maximum, maximum * secondMaximum * thirdMaximum); } public static void main(String args[]) { int arr[] = {2, 10, -5, 6, -100}; int len = arr.length; int max = maxProduct(arr, len); if (max == -1) System.out.println("No Triplet Exists"); else System.out.println("Maximum product is " + max); } }
Output:
Maximum product is 5000
core java 12 Algorithm 12 Arrays 12
COMMENTS