Codility Max Product Of Three 100% O(n) Solution

Below you can find my 100% solution to one of the Codility Lesson 6 practice challenges. The complexity of my solution is O(n) and passed all scores with 100%.

The challenge – find the max product of three elements of an array.

Task description
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 O(n) complexity solution

The problem can be solved in O(n) without sorting the array. All you need to do is find the three maximums and the two minimums of the array and that requires only one pass.

The logic behind the solution is:

• If the three maximums are all positives, their product will be the maximum.
• If the two minimums are negatives, their product will be a large positive.
• If between these 5 values there are three negatives or all of them are negatives, the maximum product will be the one between the two minimums and the maximum value of all the array.

Below, the final code:

function solution(A) {

    if (A.length === 3) {
        return A[0] * A[1] * A[2]
    }
    
    let min1, min2,max1, max2, max3
    min1 = min2 = 1001
    max1 = max2 = max3 = -1001
    
    for (let i = 0; i < A.length; i++){
        if (A[i] > max1){
            max3 = max2
            max2 = max1
            max1 = A[i]
        } else if (A[i] > max2) {
            max3 = max2
            max2 = A[i]
        } else if (A[i] > max3) {
            max3 = A[i]
        }
    
        if ( A[i] < min1) {
            min2 = min1
            min1 = A[i]
        } else if (A[i] < min2){
            min2 = A[i]
        }
    }

    prod1 = max1 * max2 * max3
    prod2 = max1 * min1 * min2

    if (prod1 > prod2) {
        return prod1
    } else {
        return prod2
    }
} 

Do you have another solution? Perhaps more efficient? Share it in the comments below!