Good morning! Hope your day has started on the right note.
In this post we will attempt to solve the Codility_ problem MaxProductOfThree using the Java programming language and the VSCode IDE on a Windows platform. We will not be using the online IDE provided by Codility_ since we will write the code on a separate computer.
Using this approach you will have to start a session each time you wish to submit code for evaluation. If you are not interested in having a test scaffold, I suggest using the online IDE provided by Codility to solve the problem.
Given a non-empty array A, return the value of the maximal product of any triplet. Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).
In this problem we are presented with an array of integers. We need to maximize the product of the different triplets and return such value.
Of course you could use a O(n**2) brute force approach, but as you probably know, it will be scoring low.
As I mentioned we will need to write a short and simple test scaffold which IS NOT PART OF THE SOLUTION.
-3, 1, 2, -2, 5, 6 main <<< arr: [-3, 1, 2, -2, 5, 6] <<< lst: [-3, 1, 2, -2, 5, 6] <<< lst: [6, 5, 2, 1, -2, -3] <<< maxVal: 60 <<< maxVal: 60 <<< maxVal: 60 main <<< result: 60 <<< maxArr: [6, 5, 2] <<< minArr: [-3, -2, 1] <<< maxVal: 60 <<< maxVal: 60 <<< maxVal: 60 <<< maxVal: 60 main <<< result: 60 -1, 2, -2, 3, -7, 4, -5, 0 main <<< arr: [-1, 2, -2, 3, -7, 4, -5, 0] <<< lst: [-1, 2, -2, 3, -7, 4, -5, 0] <<< lst: [4, 3, 2, 0, -1, -2, -5, -7] <<< maxVal: 24 <<< maxVal: 24 <<< maxVal: 140 main <<< result: 140 <<< maxArr: [4, 3, 2] <<< minArr: [-7, -5, -2] <<< maxVal: 24 <<< maxVal: 24 <<< maxVal: 140 <<< maxVal: 140 main <<< result: 140 1, 2, 4, 3 main <<< arr: [1, 2, 4, 3] <<< lst: [1, 2, 4, 3] <<< lst: [4, 3, 2, 1] <<< maxVal: 24 <<< maxVal: 24 <<< maxVal: 24 main <<< result: 24 <<< maxArr: [4, 3, 2] <<< minArr: [1, 2, 3] <<< maxVal: 24 <<< maxVal: 24 <<< maxVal: 24 <<< maxVal: 24 main <<< result: 24 -5, 5, -5, 4 main <<< arr: [-5, 5, -5, 4] <<< lst: [-5, 5, -5, 4] <<< lst: [5, 4, -5, -5] <<< maxVal: -100 <<< maxVal: 100 <<< maxVal: 125 main <<< result: 125 <<< maxArr: [5, 4, -5] <<< minArr: [-5, -5, 4] <<< maxVal: -100 <<< maxVal: 100 <<< maxVal: 125 <<< maxVal: 125 main <<< result: 125 -8, -5, -3, -2, -1, -4, 1, 3, 5 main <<< arr: [-8, -5, -3, -2, -1, -4, 1, 3, 5] <<< lst: [-8, -5, -3, -2, -1, -4, 1, 3, 5] <<< lst: [5, 3, 1, -1, -2, -3, -4, -5, -8] <<< maxVal: 15 <<< maxVal: 15 <<< maxVal: 200 main <<< result: 200 <<< maxArr: [5, 3, 1] <<< minArr: [-8, -5, -4] <<< maxVal: 15 <<< maxVal: 15 <<< maxVal: 200 <<< maxVal: 200 main <<< result: 200 -4, -6, 3, 4, 5 main <<< arr: [-4, -6, 3, 4, 5] <<< lst: [-4, -6, 3, 4, 5] <<< lst: [5, 4, 3, -4, -6] <<< maxVal: 60 <<< maxVal: 72 <<< maxVal: 120 main <<< result: 120 <<< maxArr: [5, 4, 3] <<< minArr: [-6, -4, 3] <<< maxVal: 60 <<< maxVal: 72 <<< maxVal: 120 <<< maxVal: 120 main <<< result: 120
We have a few test cases. I believe the first was provided by Codility_ as part of the problem description. Please make sure you read the problem requirements at their website before proceeding to develop a solution.
The first line of each test contains a set of integers which we need to read into an int[]. To make sure all is well so far, the contents of the int[] array are displayed.
We will be implementing two versions of the function of interest.
The first implementation displays a set of values which will help us follow the algorithm in use. When done it displays the result. The second implementation also displays some lines with values of interest. When all is said and done our test scaffold displays the result.
Note that in all the test cases the two implementations produce the same value. You can use some of the intermediate values to determine the correct answer for each test case. Even Though both implementations seem to work, the first one is slower and got a few points less than the second which received 100%.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read int[] arr ****
int[] arr = Arrays.stream(br.readLine().trim().split(", "))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** call function of interest and display result ****
System.out.println("main <<< result: " + maxProductOfThree0(arr));
// **** call function of interest and display result ****
System.out.println("main <<< result: " + maxProductOfThree(arr));
}
Our test scaffold is simple and to the point. Ir reads the values for the int[] array and displays them for us to check if all is well so far. It then calls the first implementation of the function of interest and displays the result. The process repeats with the second implementation.
/**
* Given a non-empty array A,
* return the value of the maximal product of any triplet.
*
* Check these combinations:
*
* o first 3 elements (highest values)
* o last 3 elements (lowest values – can have 2 large negative values
* that create a positive and then multipled by a positive)
* o first element and last 2 elements
* o first 2 elements and last element
*
* Runtime: O(n * log(n)) - Space: O(n)
*/
static public int maxProductOfThree0(int[] arr) {
// **** initialization - create and populate list ****
List<Integer> lst = new ArrayList<>();
for (int v : arr)
lst.add(v);
// ???? ????
System.out.println("<<< lst: " + lst.toString());
// **** sort the list - O(n * log(n)) ****
Collections.sort(lst, (a,b) -> b - a);
// ???? ????
System.out.println("<<< lst: " + lst.toString());
// **** first 3 elements ****
int maxVal = lst.get(0) * lst.get(1) * lst.get(2);
// ???? ????
System.out.println("<<< maxVal: " + maxVal);
// **** last 3 elements ****
int siz = lst.size();
int p = lst.get(siz - 1) * lst.get(siz - 2) * lst.get(siz - 3);
// **** update max value ****
if (p > maxVal) maxVal = p;
// ???? ????
System.out.println("<<< maxVal: " + maxVal);
// **** first element and last 2 elements ****
p = lst.get(0) * lst.get(siz - 1) * lst.get(siz - 2);
// **** update max value ****
if (p > maxVal) maxVal = p;
// ???? ????
System.out.println("<<< maxVal: " + maxVal);
// **** first 2 elements and last element ****
p = lst.get(0) * lst.get(1) * lst.get(siz - 1);
// **** update max value ****
if (p > maxVal) maxVal = p;
// **** return max value ****
return maxVal;
}
In this implementation we use a list. I tried using the int[] but performance was not 100% so I switched to a list. As you can see we populate the list with the contents of the int[] provided as an argument.
We then proceed to sort the list. Sorting a list or an array takes O(n * log(n)) time.
My first attempt was to return the product of the first 3 elements in the list. It works for some set of integers, but for some it does not as it is illustrated in some of the test cases. You need to consider a set of conditions which are listed in the comments section of this function.
We need to test four conditions and keep track of the highest value which we will return when done with the function of interest. The actual code is simple but necessary. Please take a few moments to read the list of conditions and understand how they work… …OK, you are back so let’s proceed.
I experimented with different approaches but performance was not 100%. I decided to go a different route.
/**
* Given a non-empty array A,
* return the value of the maximal product of any triplet.
*
* Check these combinations:
*
* o first 3 elements (highest values)
* o last 3 elements (lowest values – can have 2 large negative values
* that create a positive and then multipled by a positive)
* o first element and last 2 elements
* o first 2 elements and last element
*
* Runtime: O(n) - Space: O(6)
*/
static public int maxProductOfThree(int[] arr) {
// **** initialization ****
int[] maxArr = {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};
int[] minArr = {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE};
// **** traverse the array looking for the maximum values - O(n + 6) ****
for (int v : arr) {
// **** update max values - O(3) ****
maxValues(maxArr, v);
// **** update min values - O(3) ****
minValues(minArr, v);
}
// ???? ????
System.out.println("<<< maxArr: " + Arrays.toString(maxArr));
System.out.println("<<< minArr: " + Arrays.toString(minArr));
// **** [1] first 3 elements ****
int maxVal = maxArr[0] * maxArr[1] * maxArr[2];
// ???? ????
System.out.println("<<< maxVal: " + maxVal);
// **** [2] last 3 elements ****
int p = minArr[0] * minArr[1] * minArr[2];
if (p > maxVal) maxVal = p;
// ???? ????
System.out.println("<<< maxVal: " + maxVal);
// **** [3] first element and last 2 elements ****
p = maxArr[0] * minArr[0] * minArr[1];
if (p > maxVal) maxVal = p;
// ???? ????
System.out.println("<<< maxVal: " + maxVal);
// **** [4] first 2 elements and last element ****
p = maxArr[0] * maxArr[1] * minArr[0];
if (p > maxVal) maxVal = p;
// ???? ????
System.out.println("<<< maxVal: " + maxVal);
// **** return this product ****
return maxVal;
}
In this implementation we will not sort the array or list. We will work directly with the array looking for the max positive and the min negative values in the array.
We start by declaring `maxArr` which will hold the top max integers and the `minArr` to hold the min integers. Note that both arrays may hold a combination of all positive, all negative or a combination of both.
We then enter a loop in which we traverse the input array in O(n) time. On each pass we update both auxiliary arrays with the max values and the min values seen so far.
We then compute the four cases just as we did in the previous implementation. The function of interest returns the max value generated by the four combinations.
/**
* Auxiliary function.
* Keep 3 largest values in array.
*
* Runtime: O(3) - Space: O(0)
*/
static private void maxValues(int[] maxArr, int v) {
if (v > maxArr[0]) {
maxArr[2] = maxArr[1];
maxArr[1] = maxArr[0];
maxArr[0] = v;
} else if (v > maxArr[1]) {
maxArr[2] = maxArr[1];
maxArr[1] = v;
} else if (v > maxArr[2]) {
maxArr[2] = v;
}
}
This is the auxiliary function we use to keep track of the top three integer values in the input array.
/**
* Auxiliary function.
* Keep 3 mallest values in array.
*
* Runtime: O(3) - Space: O(0)
*/
static private void minValues(int[] minArr, int v) {
if (v < minArr[0]) {
minArr[2] = minArr[1];
minArr[1] = minArr[0];
minArr[0] = v;
} else if (v < minArr[1]) {
minArr[2] = minArr[1];
minArr[1] = v;
} else if (v < minArr[2]) {
minArr[2] = v;
}
}
This is the auxiliary function we use to keep track of the bottom three integer values in the input array.
This second implementation received 100% by Codility_.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., HackerRank, LeetCode).
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, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John