Tasks Details
easy
Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).
Task Score
100%
Correctness
100%
Performance
100%
A non-empty array A consisting of N integers is given. The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N).
For example, array A such that:
A[0] = -3 A[1] = 1 A[2] = 2 A[3] = -2 A[4] = 5 A[5] = 6contains the following example triplets:
- (0, 1, 2), product is −3 * 1 * 2 = −6
- (1, 2, 4), product is 1 * 2 * 5 = 10
- (2, 4, 5), product is 2 * 5 * 6 = 60
Your goal is to find the maximal product of any triplet.
Write a function:
class Solution { public int solution(int[] A); }
that, given a non-empty array A, returns the value of the maximal product of any triplet.
For example, given array A such that:
A[0] = -3 A[1] = 1 A[2] = 2 A[3] = -2 A[4] = 5 A[5] = 6the function should return 60, as the product of triplet (2, 4, 5) is maximal.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..100,000];
- each element of array A is an integer within the range [−1,000..1,000].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 21
Time spent on task 11 minutes
Notes
not defined yet
Code: 07:49:46 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int[] maxes = new int[3]; // maxes[0] <= maxes[1] <= maxes[2]
int[] mins = new int[2]; // mins [0] <= mins [1]
boolean foundZero = false;
// O(n)
for( int a : A )
{
updateMaxes( a, maxes );
updateMins( a, mins );
}
System.out.println(Arrays.toString(maxes));
System.out.println(Arrays.toString(mins));
int obvious = maxes[0] * maxes[1] * maxes[2];
int twoBigNegs = mins[0] * mins[1] * maxes[2];
return Math.max( obvious, twoBigNegs );
}
private static void updateMaxes( int a, int[] maxes )
{
if( a >= maxes[2] ) {
// Found new max, shift down
maxes[0] = maxes[1];
maxes[1] = maxes[2];
maxes[2] = a;
} else if( a >= maxes[1] ) {
maxes[0] = maxes[1];
maxes[1] = a;
} else if( a > maxes[0] ) {
maxes[0] = a;
}
}
private static void updateMins( int a, int[] mins )
{
if( a <= mins[0] ) {
// Found new min, shift down
mins[1] = mins[0];
mins[0] = a;
} else if( a < mins[1] ) {
mins[1] = a;
}
}
}
Analysis
Compile error
Solution.java:20: error: cannot find symbol
System.out.println(Arrays.toString(maxes));
^
symbol: variable Arrays
location: class Solution
Solution.java:21: error: cannot find symbol
System.out.println(Arrays.toString(mins));
^
symbol: variable Arrays
location: class Solution
2 errors
Code: 07:50:05 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.Arrays;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int[] maxes = new int[3]; // maxes[0] <= maxes[1] <= maxes[2]
int[] mins = new int[2]; // mins [0] <= mins [1]
boolean foundZero = false;
// O(n)
for( int a : A )
{
updateMaxes( a, maxes );
updateMins( a, mins );
}
System.out.println(Arrays.toString(maxes));
System.out.println(Arrays.toString(mins));
int obvious = maxes[0] * maxes[1] * maxes[2];
int twoBigNegs = mins[0] * mins[1] * maxes[2];
return Math.max( obvious, twoBigNegs );
}
private static void updateMaxes( int a, int[] maxes )
{
if( a >= maxes[2] ) {
// Found new max, shift down
maxes[0] = maxes[1];
maxes[1] = maxes[2];
maxes[2] = a;
} else if( a >= maxes[1] ) {
maxes[0] = maxes[1];
maxes[1] = a;
} else if( a > maxes[0] ) {
maxes[0] = a;
}
}
private static void updateMins( int a, int[] mins )
{
if( a <= mins[0] ) {
// Found new min, shift down
mins[1] = mins[0];
mins[0] = a;
} else if( a < mins[1] ) {
mins[1] = a;
}
}
}
Analysis
expand all
Example tests
1.
1.504 s
OK
stdout:
WARNING: producing output may seriously slow down your code! [2, 5, 6] [-3, -2]
Code: 07:53:12 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.Arrays;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int[] maxes = new int[3]; // maxes[0] <= maxes[1] <= maxes[2]
int[] mins = new int[2]; // mins [0] <= mins [1]
boolean foundZero = false;
// O(n)
for( int a : A )
{
updateMaxes( a, maxes );
updateMins( a, mins );
}
System.out.println(Arrays.toString(maxes));
System.out.println(Arrays.toString(mins));
int obvious = maxes[0] * maxes[1] * maxes[2];
int twoBigNegs = mins[0] * mins[1] * maxes[2];
return Math.max( obvious, twoBigNegs );
}
private static void updateMaxes( int a, int[] maxes )
{
if( a >= maxes[2] ) {
// Found new max, shift down
maxes[0] = maxes[1];
maxes[1] = maxes[2];
maxes[2] = a;
} else if( a >= maxes[1] ) {
maxes[0] = maxes[1];
maxes[1] = a;
} else if( a > maxes[0] ) {
maxes[0] = a;
}
}
private static void updateMins( int a, int[] mins )
{
if( a <= mins[0] ) {
// Found new min, shift down
mins[1] = mins[0];
mins[0] = a;
} else if( a < mins[1] ) {
mins[1] = a;
}
}
}
User test case 1:
None
User test case 2:
None
User test case 3:
None
User test case 4:
None
Analysis
expand all
Example tests
1.
1.076 s
OK
stdout:
WARNING: producing output may seriously slow down your code! [2, 5, 6] [-3, -2]
expand all
User tests
1.
0.940 s
OK
function result: 180
function result: 180
stdout:
WARNING: producing output may seriously slow down your code! [2, 5, 6] [-6, -5]
1.
0.904 s
OK
function result: 36
function result: 36
stdout:
WARNING: producing output may seriously slow down your code! [0, 1, 6] [-3, -2]
1.
0.912 s
OK
function result: 6
function result: 6
stdout:
WARNING: producing output may seriously slow down your code! [0, 0, 1] [-3, -2]
1.
0.916 s
OK
function result: 0
function result: 0
stdout:
WARNING: producing output may seriously slow down your code! [0, 0, 1] [-2, 0]
Code: 07:57:44 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can also use imports, for example:
import java.util.Arrays;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int[] maxes = {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};
// Invariant: maxes[0] <= maxes[1] <= maxes[2]
int[] mins = {Integer.MAX_VALUE, Integer.MAX_VALUE}
// Invariant: mins[0] <= mins[1]
// O(n)
for( int a : A )
{
updateMaxes( a, maxes );
updateMins( a, mins );
}
System.out.println(Arrays.toString(maxes));
System.out.println(Arrays.toString(mins));
int obvious = maxes[0] * maxes[1] * maxes[2];
int twoBigNegs = mins[0] * mins[1] * maxes[2];
return Math.max( obvious, twoBigNegs );
}
private static void updateMaxes( int a, int[] maxes )
{
if( a >= maxes[2] ) {
// Found new max, shift down
maxes[0] = maxes[1];
maxes[1] = maxes[2];
maxes[2] = a;
} else if( a >= maxes[1] ) {
maxes[0] = maxes[1];
maxes[1] = a;
} else if( a > maxes[0] ) {
maxes[0] = a;
}
}
private static void updateMins( int a, int[] mins )
{
if( a <= mins[0] ) {
// Found new min, shift down
mins[1] = mins[0];
mins[0] = a;
} else if( a < mins[1] ) {
mins[1] = a;
}
}
}
Analysis
Compile error
Solution.java:13: error: ';' expected
int[] mins = {Integer.MAX_VALUE, Integer.MAX_VALUE}
^
1 error
Code: 07:57:56 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can also use imports, for example:
import java.util.Arrays;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int[] maxes = {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};
// Invariant: maxes[0] <= maxes[1] <= maxes[2]
int[] mins = {Integer.MAX_VALUE, Integer.MAX_VALUE};
// Invariant: mins[0] <= mins[1]
// O(n)
for( int a : A )
{
updateMaxes( a, maxes );
updateMins( a, mins );
}
System.out.println(Arrays.toString(maxes));
System.out.println(Arrays.toString(mins));
int obvious = maxes[0] * maxes[1] * maxes[2];
int twoBigNegs = mins[0] * mins[1] * maxes[2];
return Math.max( obvious, twoBigNegs );
}
private static void updateMaxes( int a, int[] maxes )
{
if( a >= maxes[2] ) {
// Found new max, shift down
maxes[0] = maxes[1];
maxes[1] = maxes[2];
maxes[2] = a;
} else if( a >= maxes[1] ) {
maxes[0] = maxes[1];
maxes[1] = a;
} else if( a > maxes[0] ) {
maxes[0] = a;
}
}
private static void updateMins( int a, int[] mins )
{
if( a <= mins[0] ) {
// Found new min, shift down
mins[1] = mins[0];
mins[0] = a;
} else if( a < mins[1] ) {
mins[1] = a;
}
}
}
User test case 1:
None
User test case 2:
None
User test case 3:
None
User test case 4:
None
Analysis
expand all
Example tests
1.
1.136 s
OK
stdout:
WARNING: producing output may seriously slow down your code! [2, 5, 6] [-3, -2]
expand all
User tests
1.
1.060 s
OK
function result: 180
function result: 180
stdout:
WARNING: producing output may seriously slow down your code! [2, 5, 6] [-6, -5]
1.
0.960 s
OK
function result: 36
function result: 36
stdout:
WARNING: producing output may seriously slow down your code! [0, 1, 6] [-3, -2]
1.
0.968 s
OK
function result: 6
function result: 6
stdout:
WARNING: producing output may seriously slow down your code! [-3, -2, 1] [-3, -2]
1.
0.952 s
OK
function result: 0
function result: 0
stdout:
WARNING: producing output may seriously slow down your code! [-2, 0, 1] [-2, 0]
Code: 07:58:51 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can also use imports, for example:
import java.util.Arrays;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int[] maxes = {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};
// Invariant: maxes[0] <= maxes[1] <= maxes[2]
int[] mins = {Integer.MAX_VALUE, Integer.MAX_VALUE};
// Invariant: mins[0] <= mins[1]
// O(n)
for( int a : A )
{
updateMaxes( a, maxes );
updateMins( a, mins );
}
System.out.println(Arrays.toString(maxes));
System.out.println(Arrays.toString(mins));
int obvious = maxes[0] * maxes[1] * maxes[2];
int twoBigNegs = mins[0] * mins[1] * maxes[2];
return Math.max( obvious, twoBigNegs );
}
private static void updateMaxes( int a, int[] maxes )
{
if( a >= maxes[2] ) {
// Found new max, shift down
maxes[0] = maxes[1];
maxes[1] = maxes[2];
maxes[2] = a;
} else if( a >= maxes[1] ) {
maxes[0] = maxes[1];
maxes[1] = a;
} else if( a > maxes[0] ) {
maxes[0] = a;
}
}
private static void updateMins( int a, int[] mins )
{
if( a <= mins[0] ) {
// Found new min, shift down
mins[1] = mins[0];
mins[0] = a;
} else if( a < mins[1] ) {
mins[1] = a;
}
}
}
User test case 1:
None
User test case 2:
None
User test case 3:
None
User test case 4:
None
Analysis
expand all
Example tests
1.
1.528 s
OK
stdout:
WARNING: producing output may seriously slow down your code! [2, 5, 6] [-3, -2]
expand all
User tests
1.
1.488 s
OK
function result: 180
function result: 180
stdout:
WARNING: producing output may seriously slow down your code! [2, 5, 6] [-6, -5]
1.
1.496 s
OK
function result: 36
function result: 36
stdout:
WARNING: producing output may seriously slow down your code! [0, 1, 6] [-3, -2]
1.
1.472 s
OK
function result: 6
function result: 6
stdout:
WARNING: producing output may seriously slow down your code! [-3, -2, 1] [-3, -2]
1.
1.480 s
OK
function result: 0
function result: 0
stdout:
WARNING: producing output may seriously slow down your code! [-2, 0, 1] [-2, 0]
Code: 07:59:09 UTC,
java,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can also use imports, for example:
import java.util.Arrays;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int[] maxes = {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};
// Invariant: maxes[0] <= maxes[1] <= maxes[2]
int[] mins = {Integer.MAX_VALUE, Integer.MAX_VALUE};
// Invariant: mins[0] <= mins[1]
// O(n)
for( int a : A )
{
updateMaxes( a, maxes );
updateMins( a, mins );
}
System.out.println(Arrays.toString(maxes));
System.out.println(Arrays.toString(mins));
int obvious = maxes[0] * maxes[1] * maxes[2];
int twoBigNegs = mins[0] * mins[1] * maxes[2];
return Math.max( obvious, twoBigNegs );
}
private static void updateMaxes( int a, int[] maxes )
{
if( a >= maxes[2] ) {
// Found new max, shift down
maxes[0] = maxes[1];
maxes[1] = maxes[2];
maxes[2] = a;
} else if( a >= maxes[1] ) {
maxes[0] = maxes[1];
maxes[1] = a;
} else if( a > maxes[0] ) {
maxes[0] = a;
}
}
private static void updateMins( int a, int[] mins )
{
if( a <= mins[0] ) {
// Found new min, shift down
mins[1] = mins[0];
mins[0] = a;
} else if( a < mins[1] ) {
mins[1] = a;
}
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N * log(N))
expand all
Example tests
1.
1.512 s
OK
stdout:
WARNING: producing output may seriously slow down your code! [2, 5, 6] [-3, -2]
expand all
Correctness tests
1.
1.424 s
OK
stdout:
WARNING: producing output may seriously slow down your code! [1000, 1000, 1000] [1000, 1000]
1.
1.456 s
OK
stdout:
WARNING: producing output may seriously slow down your code! [1, 4, 5] [0, 1]
1.
1.468 s
OK
stdout:
WARNING: producing output may seriously slow down your code! [2, 3, 100] [-1000, 2]
1.
1.464 s
OK
stdout:
WARNING: producing output may seriously slow down your code! [974, 993, 997] [-981, -965]
expand all
Performance tests
1.
1.500 s
OK
stdout:
WARNING: producing output may seriously slow down your code! [998, 999, 1000] [-1000, -999]
1.
1.504 s
OK
stdout:
WARNING: producing output may seriously slow down your code! [1000, 1000, 1000] [-1000, -1000]
1.
1.680 s
OK
stdout:
WARNING: producing output may seriously slow down your code! [1000, 1000, 1000] [-1000, -1000]
1.
1.448 s
OK
stdout:
WARNING: producing output may seriously slow down your code! [10, 10, 500] [-1000, -10]
1.
1.748 s
OK
stdout:
WARNING: producing output may seriously slow down your code! [-1000, -1000, -1000] [-1000, -1000]