solve maximum product of three array elements without sorting

Question

There is a variety of answers for the MaxProductOfThree task on codility.com, most of them involving a sorting algorithm.

The problem is:

A non-empty zero-indexed array A consisting of N integers is given.

The problem is to find the maximum product of 3 elements from given array.

The length of the array is between 3 and 100,000

each element of array A is an integer within the range [−1,000..1,000]

    expected worst-case time complexity is O(N*log(N));

    expected worst-case space complexity is O(1), 

beyond input storage (not counting the storage required for input arguments). Example:

  a[0] = -3;
  a[1] = 7;
  a[2] = 2;
  a[3] = 1;
  a[4] = 5;
  a[5] = 7;

the max product is a[1]*a[4]*a[5] = 245

Is there a linear-time solution to this problem, besides the O(n log n) approach that involves sorting?

Answer 1

There are only two possible options for the max product in a sorted array.

1) The largest (the last) three elements

2) Combination of two smallest and the largest elements (in case of negative elements, a product of two negatives is positive which multiplied with the largest element, if positive, of an array can produce the largest product)

So the solution is a max of the two and nothing else. The below got 100/100 on Codility.

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.Arrays;

class Solution {

    public int solution(int[] A) {

        int N = A.length;
        Arrays.sort(A);

        /**
         * When we sort an array there are two possible options for the largest product
         * 1) The largest (the last) three elements
         * 2) Combination of two smallest and the largest elements
         * Logic of (1): Obvious
         * Logic of (2): A pair of negatives multiplied returns a positive, which in combination with 
         * the largest positive element of the array can give the max outcome.
         * Therefore we return the max of options (1) and (2)
         */
        return Math.max(A[0] * A[1] * A[N - 1], A[N - 1] * A[N - 2] * A[N - 3]);
    }
}

Cheers