Max Product of Three (A problem on sorting technique)

MaxProductOfThree

Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).

Complexity: Easy

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).

Your goal is to find the maximal product of any triplet.

Write a function:

def solution(A)

that, given a non-empty array A, returns the value of the maximal product of any triplet.

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].

Example

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

The function should return 60, as the product of triplet (2, 4, 5) is maximal.

Code

def solution(A):
    A.sort()
    # multiplication two large negative numbers with a positive number
    p = A[0] * A[1] * A[-1]
    
    # multiplication of three positive numbers 
    q = A[-1] * A[-2] * A[-3]
    return max(p, q)

Detected time complexity:
O(N * log(N))

Tests

Correctness tests

one_triple

three elements

simple1

simple tests

simple2

simple tests

small_random

random small, length = 100

Performance tests

medium_range

-1000, -999, ... 1000, length = ~1,000

medium_random

random medium, length = ~10,000

large_random

random large, length = ~100,000

large_range

2000 * (-10..10) + [-1000, 500, -1]

extreme_large

(-2, .., -2, 1, .., 1) and (MAX_INT)..(MAX_INT), length = ~100,000

Tags: Technology,Algorithms,Python