MaxProductOfThree at app.codility.com/programmers in C++ Explained: Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N * log(N))
Lesson 6 at app.codility.com/programmers
The solution and its explanation are given below.
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 2 Jul 2025
Problem
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] = 6
contains 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:
int solution(vector<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] = 6
the 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].
Note
It is not the number of triplets that has been asked for. It is not the indexes of any triplet that have been asked for. It is the maximum product of a triplet of any combination of the elements, that has been asked for. The indexes do not have to be consecutive.This tutorial (lesson) is on sorting, so it should occur to the reader that sorting is needed in the solution. If the list is sorted, the sorted list can be scanned from the beginning to the end to find the maximum product. However, in this extra n time, each pass though the function has many steps, and all that does not lead to 100% performance at app.codility.com/programmers.
It is possible to reduce the extra O(n) time to O(1) time (constant time), leading to an expected time complexity of O(n.log2n + 1).
Strategy
All Positive Numbers
Assume that the sorted list consists of only positive numbers as follows:
1, 2, 3, 4, 5, 6
It can clearly be seen here that the maximum product is from the last three numbers giving, 4 x 5 x 6 = 120.
All Negative Numbers
Assume that the sorted list consists of only negative numbers as follows:-6, -5, -4, -3, -2, -1
Again, it can clearly be seen here that the maximum product is still from the last three numbers giving, -3 x -2 x -1 = -6. The product of the first three numbers here is -6 x -5 x -4 = -120, which is far less than -6. The number-line has to be respected here.
Mix of Positive and Negative Numbers
The reader should accept without proof here, that in this situation, the product of the first and second elements with the last element, may actually be the maximum product; so it has to be compared with the product of the last three elements, in order to choose the higher. That is A[0] x A[1] x A[N-1] and A[N-1] x A[N-2] x A[N-3] have to be compared, in order to choose the higher. The reader should consult some other document for the proof.This case alone takes care of the cases of all positive numbers or all negative numbers.
Case with Only Three Elements
One of the assumptions in the given problem is:• N is an integer within the range [3..100,000];
This means the minimum length of the list is 3. So the given list can have only 3 elements. In this case the product of the three elements is returned as the answer, whether the list has been sorted or not (multiplication is commutative).
It can be cumbersome to solve the problem, the brute-force way; so only the smart approach is presented here:
Smart Approach
The programmer may not know if all the elements are negative or if all are positive or are mixed. So the following program should always be used. Based on the strategy above, the smart solution is in the following program (read through the code):#include <iostream>Note that the programmer has not defined his/her own sorting function. The algorithm library provides the sort() function.
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> &A) {
int N = A.size();
sort(A.begin(), A.end());
if (N==3)
return (A[0]*A[1]*A[2]);
else {
int r1 = A[N-1]*A[N-2]*A[N-3];
int r2 = A[0]*A[1]*A[N-1];
return (r1>r2?r1:r2);
}
}
int main()
{
vector<int> P{-3, 1, 2, -2, 5, 6};
int ret = solution(P);
cout << ret <<'\n';
return 0;
}
At app.codility.com/programmers the scoring and detected time complexity for this smart solution() function is:
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N * log(N))
The added time for the following statements were ignored at app.codility.com/programmers:
int r1=A[N-1]*A[N-2]*A[N-3];
int r2=A[N-1]*A[0]*A[1];
There are actually six operations here, which are: =, *, *, =, *, *
Thanks for reading.