I want to find the maximum product that can be obtained from any 3 integers in an integer array. The optimal solution has time complexity of \$O(n)\$ and space complexity of \$O(1)\$. I managed to write up as solution in Java that only traverses the array twice (so my time complexity is \$O(n)\$) and my space complexity is \$O(1)\$. I do not believe the solution can be any cleaner than this but would still like to see what other people think.
The \$O(n)\$ solution is obtained by keeping track of the max three integers and the min two integers. The max product will either be (min_one * min_two * max_one
) or (max_one * max_two * max_three
).
// Assume input array is of at least length 3.
public int max_prod_three(int[] A){
int len = A.length;
// Base case
if (len == 3) return A[0]*A[1]*A[2];
int max = A[0], min = A[0], max_index = 0, min_index = 0;
for (int i = 0; i < len; i++) {
if (A[i] > max) {
max = A[i];
max_index = i;
}
else if (A[i] < min) {
min = A[i];
min_index = i;
}
}
int max_sec = min, max_third = min , min_sec = max;
for (int i = 0; i < len; i++) {
if (i == max_index || i == min_index) continue;
if (A[i] > max_sec) {
max_third = max_sec;
max_sec = A[i];
}
else if (A[i] > max_third) {
max_third = A[i];
}
if (A[i] < min_sec) min_sec = A[i];
}
int prod_one = max * max_sec * max_third ;
int prod_two = min * min_sec * max ;
if (prod_one > prod_two) return prod_one ;
return prod_two;
}
You can iterate through the array only once and get the max product but I found that the solution gets a bit too messy (with a lot more if
else
statements). But if anyone can do it cleanly, I would like to know.
max_prod_three(Integer[] A)
? \$\endgroup\$ – Spotted Oct 30 '15 at 7:21