In this post we will revisit a practice question Largest Triple Products. Not sure if today this question would be of interest to Facebook and /or to Meta Platforms technical job seekers.
My original post Largest Triple Products was superseded by Largest Triple Products – Revisited and by this latest post.
The motivation for this post came from a question left by Brent Boyer which suggested an implementation for the function of interest. I have included it in this post as `findMaxProduct3`.
You're given a list of n integers arr[0..(n-1)]. You must compute a list output[0..(n-1)] such that, for each index i (between 0 and n-1, inclusive), output[i] is equal to the product of the three largest elements out of arr[0..i] (or equal to -1 if i < 2, as arr[0..i] then includes fewer than three elements). Note that the three largest elements used to form any product may have the same values as one another, but they must be at different indices in arr. Input: o n is in the range [1, 100,000]. o Each value arr[i] is in the range [1, 1,000]. Output: Return a list of n integers output[0..(n-1)], as described above.
This is the original text for the problem description. I am not sure if it is still valid for the current version of the problem if it is still available.
int[] findMaxProduct(int[] arr) {
}
The signature for the function of interest in Java has not changed.
1,2,3,4,5 main <<< arr: [1, 2, 3, 4, 5] main <<< findMaxProduct0: [-1, -1, 6, 24, 60] main <<< findMaxProduct1: [-1, -1, 6, 24, 60] main <<< findMaxProduct2: [-1, -1, 6, 24, 60] main <<< findMaxProduct3: [-1, -1, 6, 24, 60] 2,1,2,1,2 main <<< arr: [2, 1, 2, 1, 2] main <<< findMaxProduct0: [-1, -1, 4, 4, 8] main <<< findMaxProduct1: [-1, -1, 4, 4, 8] main <<< findMaxProduct2: [-1, -1, 4, 4, 8] main <<< findMaxProduct3: [-1, -1, 4, 4, 8] 1,2,3,4,3,2,1 main <<< arr: [1, 2, 3, 4, 3, 2, 1] main <<< findMaxProduct0: [-1, -1, 6, 24, 36, 36, 36] main <<< findMaxProduct1: [-1, -1, 6, 24, 36, 36, 36] main <<< findMaxProduct2: [-1, -1, 6, 24, 36, 36, 36] main <<< findMaxProduct3: [-1, -1, 6, 24, 36, 36, 36] -2 main <<< n: 67680 main <<< findMaxProduct0: 16 ms main <<< findMaxProduct1: 2 ms main <<< findMaxProduct2: 1 ms main <<< findMaxProduct3: 1 ms -2 main <<< n: 85454 main <<< findMaxProduct0: 17 ms main <<< findMaxProduct1: 3 ms main <<< findMaxProduct2: 2 ms main <<< findMaxProduct3: 1 ms -2 main <<< n: 43555 main <<< findMaxProduct0: 14 ms main <<< findMaxProduct1: 1 ms main <<< findMaxProduct2: 1 ms main <<< findMaxProduct3: 1 ms -2 main <<< n: 12685 main <<< findMaxProduct0: 13 ms main <<< findMaxProduct1: 0 ms main <<< findMaxProduct2: 0 ms main <<< findMaxProduct3: 0 ms -2 main <<< n: 24203 main <<< findMaxProduct0: 15 ms main <<< findMaxProduct1: 1 ms main <<< findMaxProduct2: 0 ms main <<< findMaxProduct3: 1 ms
Each test case is separated from the other by two blank lines.
The first line is the input line. It holds a list of integers which will be used to populate an int[] array which will be used as the int[] arr argument to the function of interest. In addition if you wish to test larger input arrays, you may enter a single “-2”. This will populate a large array with random integer values.
Our test scaffold which IS NOT PART OF THE SOLUTION, reads the input line. Based on the contents it populates the int[] `arr` with the specified set of numbers or generates a large array with random numbers.
If you specify a list of integers as shown in the first three test cases, the test scaffold displays the contents of the int[] `arr` for us to verify all is well before calling the four implementations of the function of interest.
If you specify “-2” the contents of the input array are not displayed. Instead the number of random values is displayed as illustrated by the variable `n`.
The results as required are displayed only for the test cases in which the input values are specified. For the test cases with a large number of values, the time in milliseconds is displayed instead.
Before we look at the actual code, please take a moment to look at the results of the test cases.
Without a doubt the first implementation of the function of interest is the slowest. We will see why as we look at the code for the implementation.
The other three implementations are close and for many test cases which I have not included, the execution time improves from top to bottom. That said, you always need to check different implementations against the actual input data.
/**
* Test scaffolding
*
* !!!! NOT PART OF SOLUTION !!!!
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** declare arr ****
int[] arr = null;
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read and split strings with integers ****
String[] strs = br.readLine().trim().split(",");
// **** close buffered reader ****
br.close();
// **** check if we need to generate our own array of values ****
if (strs.length == 1 && strs[0].equals("-2")) {
// **** ****
Random rand = new Random();
// **** generate n ****
int n = rand.nextInt(100000);
// ???? ????
System.out.println("main <<< n: " + n);
// **** create arr ****
arr = new int[n];
// **** populate arr ****
for (var i = 0; i < n; i++)
arr[i] = rand.nextInt(1000);
} else {
// **** create integer arr from string values ****
arr = Arrays.stream(strs)
.mapToInt(Integer::parseInt)
.toArray();
}
// **** short arrays ****
if (arr.length < 16) {
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** find the max products and display result (take 1) ****
System.out.println("main <<< findMaxProduct0: " + Arrays.toString(findMaxProduct0(arr)));
// **** find the max products and display result (take 2) ****
System.out.println("main <<< findMaxProduct1: " + Arrays.toString(findMaxProduct1(arr)));
// **** find the max products and display result (take 3) ****
System.out.println("main <<< findMaxProduct2: " + Arrays.toString(findMaxProduct2(arr)));
// **** find the max products and display result (take 4) ****
System.out.println("main <<< findMaxProduct3: " + Arrays.toString(findMaxProduct3(arr)));
} else {
// **** ****
for (var i = 0; i < 4; i++) {
// **** start timer ****
long start = System.currentTimeMillis();
// **** call function of interest ****
switch (i) {
case 0:
findMaxProduct0(arr);
break;
case 1:
findMaxProduct1(arr);
break;
case 2:
findMaxProduct2(arr);
break;
case 3:
findMaxProduct3(arr);
break;
default:
System.err.println("main <<< UNEXPECTED i: " + i);
System.exit(-1);
break;
}
// **** stop timer ****
long end = System.currentTimeMillis();
// **** display execution time ****
System.out.println("main <<< findMaxProduct" + i + ": " + (end - start) + " ms");
}
}
This is the test test scaffold which IS NOT PART OF THE SOLUTION, and was modified from the previous two posts.
The code checks the input line if the user entered a “-2”. If so a random number is generated for the size of the array. The array is then populated with random values.
If a set of int values is offered to the program, the `arr` is populated with such values and the contents of the int[] `arr` is displayed. This is done to verify that all is well before calling the different implementations of the function of interest.
If we are dealing with short length arrays, we call the four different implementations and display the returned values. We can use such test cases to verify that the different implementations return the same results and that the values match.
Due to the size of the large arrays, we collect the `start` time, call an implementation of the function of interest, collect the `end` time and display time the implementation took to process the data.
/**
* Uses a priority queue.
*/
static int[] findMaxProduct0(int[] arr) {
// **** sanity check(s) ****
if (arr == null) return null;
if (arr.length == 0) return new int[0];
if (arr.length == 1) return new int[] {-1};
if (arr.length == 2) return new int[] {-1, -1};
// **** initialization ****
int[] prods = new int[arr.length];
prods[0] = prods[1] = -1;
int prod = arr[0] * arr[1] * arr[2];
prods[2] = prod;
PriorityQueue<Integer> maxVals = new PriorityQueue<Integer>( (a,b) -> (a - b) );
maxVals.add(arr[0]);
maxVals.add(arr[1]);
maxVals.add(arr[2]);
// **** traverse array O(n) ****
for (int i = 3; i < arr.length; i++) {
// **** update max values (if needed) ****
if (arr[i] > maxVals.peek()) {
// **** remove from head of the queue (smallest value) ****
maxVals.remove();
// **** add new highest value ****
maxVals.add(arr[i]);
// **** compute the max product ****
Integer[] tmp = (Integer[]) maxVals.toArray(new Integer[0]);
prod = tmp[0] * tmp[1] * tmp[2];
}
// **** set the max product in the array ****
prods[i] = prod;
}
// **** return array of max products ****
return prods;
}
This first implementation of the function of interest uses a priority queue.
This function has been slightly edited. If interested in additional comments please refer to the first post in this series.
/**
* Edited previous implementation.
* Uses array of thee largest values.
*/
static int[] findMaxProduct1(int[] arr) {
// **** sanity check(s) ****
if (arr == null) return null;
if (arr.length == 0) return new int[0];
if (arr.length == 1) return new int[] {-1};
if (arr.length == 2) return new int[] {-1, -1};
// **** initialization ****
int[] prods = new int[arr.length];
prods[0] = prods[1] = -1;
int prod = arr[0] * arr[1] * arr[2];
prods[2] = prod;
// **** compute the largest three values and return them in the array ****
int[] largest = new int[] {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};
for (int i = 0; i < 3; i++)
largest = largestValues(largest, arr[i]);
// **** traverse array multiplying the current 3 largest entries O(n) ****
for (int i = 3; i < arr.length; i++) {
// **** update the top three largest values ****
largest = largestValues(largest, arr[i]);
// **** generate the product of the three largest values ****
prods[i] = largest[0] * largest[1] * largest[2];
}
// **** return array of max products ****
return prods;
}
In this implementation which was in the previous post in this blog, we use an array of three integers named `largest` in which we keep the largest integers we have encountered so far as we traverse the input int[] `arr`.
/**
* Largest values in descending order.
*
* Utility method.
*/
static private int[] largestValues(int[] largest, int val) {
// **** update the top three values ****
if (val > largest[0]) {
largest[2] = largest[1];
largest[1] = largest[0];
largest[0] = val;
}
// **** update the top two values ****
else if (val > largest[1]) {
largest[2] = largest[1];
largest[1] = val;
}
// **** update the top value ****
else if (val > largest[2]) {
largest[2] = val;
}
// **** return the top three values ****
return largest;
}
This is an auxiliary function which is used to keep the three values in the specified array in ascending order. It does so by inserting the int `val` and updating the other two values as needed to keep the int[] `arr` in ascending order.
For additional information please refer to the second post in this blog in this series.
/**
* Single sort of three elements.
*/
static int[] findMaxProduct2(int[] arr) {
// **** sanity check(s) ****
if (arr == null) return null;
if (arr.length == 0) return new int[] {};
if (arr.length == 1) return new int[] { -1 };
if (arr.length == 2) return new int[] { -1, -1 };
// **** initialization ****
int[] prods = new int[arr.length];
prods[0] = prods[1] = -1;
int prod = arr[0] * arr[1] * arr[2];
prods[2] = prod;
int[] tops = new int[]{ arr[0], arr[1], arr[2]};
// **** sort tops array - O(3 log(3)) ****
Arrays.sort(tops);
// **** process array - O(n) ****
for (var i = 3; i < arr.length; i++) {
// **** skip this arr entry ****
for ( ; i < arr.length && arr[i] < tops[0]; i++)
prods[i] = prods[i - 1];
// **** check if done processing arr ****
if (i >= arr.length) break;
// **** update all three entries ****
if (arr[i] > tops[2]) {
tops[0] = tops[1];
tops[1] = tops[2];
tops[2] = arr[i];
}
// **** update two entries ****
else if (arr[i] > tops[1]) {
tops[0] = tops[1];
tops[1] = arr[i];
}
// **** update one entry ****
else if (arr[i] > tops[0]) {
tops[0] = arr[i];
}
// **** compute and save product ****
prods[i] = tops[0] * tops[1] * tops[2];
}
// **** return array of max products ****
return prods;
}
In this implementation we will use the `prods` array to keep the results as we traverse the input array.
The int[] `tops` array of three elements is initialized with the first three values from the int[] `arr` and then is sorted by calling the `Arrays.sort` method.
The main loop is used to maintain the int[] `tops` array in ascending order.
The `for` loop skips `arr` entries that are lower in value than the first `tops` entry.
For an entry that is larger we update an entry in the `tops` array. We do this by checking the current `arr` value and comparing it to the last, middle or first entry in `tops`. By making modifications in one of the cases, the `tops` array is kept in monotonically ascending order.
Since the `tops` array has changed, the associated entry in `prods` is updated with the newly computed value.
When all is said and done the function of interest returns the `prods` array.
/**
* Contributed by Brent Boyer.
*
* Multiple three element sorts.
*/
static int[] findMaxProduct3(int[] arr) {
// **** sanity check(s) ****
if (arr == null) return null;
if (arr.length == 0) return new int[0];
if (arr.length == 1) return new int[] {-1};
if (arr.length == 2) return new int[] {-1, -1};
// **** ****
int[] result = new int[arr.length];
result[0] = -1;
result[1] = -1;
result[2] = arr[0] * arr[1] * arr[2];
int[] largest3 = new int[3];
largest3[0] = arr[0];
largest3[1] = arr[1];
largest3[2] = arr[2];
// **** sort largest array - O(3 log(3)) ****
Arrays.sort(largest3);
// **** ****
int productLast = result[2];
// **** for top performance, since 3 is such a small number,
// use inline the code to insert arr[i] into its proper
// slot and drop the original largest3[0] ****
for (int i = 3; i < arr.length; i++) {
// **** sort and compute product ****
if (arr[i] > largest3[0]) {
// **** replace smallest ****
largest3[0] = arr[i];
// **** sort largest array - O(3 log(3)) ****
Arrays.sort(largest3);
// **** compute product ****
productLast = largest3[0] * largest3[1] * largest3[2];
}
// **** store product ****
result[i] = productLast;
}
// **** return products ****
return result;
}
This implementation of the function of interest was provided by Brent Boyer. I made simple editing modifications so the code would be consistent with previous implementations of the function of interest.
What is different in this implementation is that instead of keeping the int[] `largest` array of three elements sorted by manipulating the entries, it just replaces the smallest entry found in `largest[0]` with the current `arr[i]` and then calls the `Arrays.sort` method.
I found this approach very interesting and as you can see in our results, it seems to perform in most cases, better than the other three implementations. If interested you can get the code for this post from GitHub and experiment with it to gain a deeper understanding of this O(n log(n)) sort function in action.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named LargestTripleProducts.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge, and enhance your developer / engineering toolset.
Thanks for reading this post and feel free to connect with me John Canessa on LinkedIn.
Enjoy;
John