Max Product Of Three

19 Apr, 2021

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:

function solution(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].

My Solution

success O(N * log(N))

function solution(A) {
	A.sort((a, b) => a - b);
	let multiplyBottomLine = A[0] * A[1];
	let multiplySecondThirdLargest = A[A.length - 3] * A[A.length - 2];
	let isMinusArray = A.every((v) => v < 0);

	if (
		!isMinusArray &&
		multiplyBottomLine > 0 &&
		multiplySecondThirdLargest < multiplyBottomLine
	) {
		return A[A.length - 1] * multiplyBottomLine;
	}

	return A[A.length - 1] * multiplySecondThirdLargest;
}

https://app.codility.com/demo/results/training5YEY4B-KNJ/

success O(N * log(N))

function solution(A) {
	// first we order it
	A.sort((a, b) => a - b);

	// we see the first two possibilities and we compare them
	let val1 = A[A.length - 1] * A[A.length - 2] * A[A.length - 3];
	let val2 = A[A.length - 1] * A[0] * A[1];

	// we return the higher value
	if (val1 > val2) {
		return val1;
	} else {
		return val2;
	}
}