CareerCup

@aonecoding,
if you look into your own algorithm, I can see there is a solution in exact n. I dislike O, I like Theta. So yes, in Theta(n).

Let's assume that the array has at *least three entries* and that we pick numbers from the array *without replacement*.

The solution is trivial if the array only contains positive numbers. In fact even if there's one negative number in the array, the solution is:

case_0 = prod( nlargest( 3, array ) )

Here, nlargest can be implemented using a heap. In case there are two or more negative numbers in the array, we need to handle two distinct cases (due to the fact that two negative numbers can yield a large positive product).

case_1 = prod( nlargest( 3, array ) )
case_2 = prod( max( array ) * nsmallest( 2, array ) )

Thus, the final solution that handles all cases (including case_0 which is identical to case_1) in linear time is:

max( case_1, case_2 )

A specific implementation in Python might be:

from heapq import nsmallest, nlargest
from numpy import prod
from itertools import combinations


def max_prod3(arr):
    case_1 = prod(nlargest(3, arr))
    case_2 = max(arr) * prod(nsmallest(2, arr))
    return max(case_1, case_2)


def test_max_prod3(arr):
    # compare with brute-force solution
    correct = max(prod(triplet) for triplet in combinations(arr, 3))
    assert max_prod3(arr) == correct, "incorrect result for input {}".format(arr)

public int largestProduct3(int[] array) {

        Arrays.sort(array);

        int n = array.length;
        int maxProduct;

        //case> pick the last 3 numbers(when the array has only negative, or only positive numbers)
        maxProduct = array[n - 1] * array[n - 2] * array[n - 3];

        //case> pick 2 numbers from the left end and 1 number from the right end
        maxProduct = Math.max(maxProduct, array[0] * array[1] * array[n - 1]);

        return maxProduct;
    }

Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.

Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy and other advanced algo problems),
and mock interviews.

Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.

Welcome to email us aonecoding@gmail.com with any questions. Thanks for reading.

The solution isn't that good.Complexity is O(nlogn) as you sort. we can do better.

if the array is only positive integers you can do it in O(n)
int max1 = int.MinValue;
int max2 = int.MinValue;
int max3 = int.MinValue;

for(int i = 0; i <A.Length;i++)
{
if(A[i] > max1)
{
max3 = max2;
max2 = max1;
max1 = A[i];
}
if(A[i] > max2)
{
max3 = max2;
max2 = A[i];
}
if (A[i] > max3)
max3 = A[i];
}

Console.WriteLine(max1 * max2 * max3);

if the array is only positive integers, you can do it in O(n)

int max1 = int.MinValue;
            int max2 = int.MinValue;
            int max3 = int.MinValue;

            for(int i  = 0; i <A.Length;i++)
            {
                if(A[i] > max1)
                {
                    max3 = max2;
                    max2 = max1;
                    max1 = A[i];                    
                }
                if(A[i] > max2)
                {
                    max3 = max2;
                    max2 = A[i];
                }
                if (A[i] > max3)
                    max3 = A[i];
            }

            Console.WriteLine(max1 * max2 * max3);

If the array contains only positive integers then one can do it in O(n) ...

int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        int max3 = Integer.MIN_VALUE;

        for(int 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];
        }
        System.out.println("Maximum product : " + (max1 * max2 * max3));

void max3(int& m1, int& m2, int& m3){
		int max = max(max(m1,m2),m3);
             	int min = min(min(m1,m2),m3);
                m2 = (m1+m2+m3) - max - min;
                m1 = max;
 		m3 = min; 
	}

	int findMaxProduct(const vector<int>& v1){
	        int sz = v.size();
        	int m1 = v[0], m2 = v[1] , m3 = v[2];
        	max3(m1, m2, m3);


	        for(int i=3; i<sz; i++){
        	        if(v[i] > m3){
                	        m3 = v[i];
                        	max3(&m1, &m2, &m3);
                	}
        	}

        	cout << m1 * m2 * m3;	
	}

Actually, since the question is about multiplying the three maximum numbers we can still achieve a O(n) for whatever numbers beings used by using additional data structure such as hash map which contains a maximum numbers as a key and frequency of that number as a value. Basically, the idea would be to insert maximums in a hash map with their frequency. if that frequency is greater than or equal 3, then we are done. If it is 2, we are missing the third maximum, if only 1, that means we are missing the other 2 maximums. So, the idea here is to iterate over the array 3 times which is O(3n).

if all is positive: a*b*c is largest if you pick the largest three numbers
if negative numbers are alowed, you have two cases, the product of the two smallest and the largest or the product the three largest

to find the three largest and two smallest numbers iterate over the array and pick this numers out (as if you would only scan for max or min). The thing is k-Selection and leads to O(n*k), but if k is constant, it's O(n) and if k is small it's reasonable efficient (among others due to caches on the CPU)

then calculate the two cases and return the max of them.

done.

if you need coaching... ;-)

Time complexity: O(N)

int MaxProd3(vector<int> const &a)
{
    int max_prod3 = 0;
    if (a.size() >= 3) {
        int max_val = max(a[0], a[1]);
        int max_prod2 = a[0] * a[1];
        int min_val = min(a[0], a[1]);
        int min_prod2 = a[0] * a[1];
        max_prod3 = a[0] * a[1] * a[2];
        for (int i = 2; i < a.size(); ++i) {
            max_prod3 = max(max_prod3, a[i] * max_prod2);
            max_prod3 = max(max_prod3, a[i] * min_prod2);
            max_prod2 = max(max_prod2, max_val * a[i]);
            max_prod2 = max(max_prod2, min_val * a[i]);
            min_prod2 = min(min_prod2, max_val * a[i]);
            min_prod2 = min(min_prod2, min_val * a[i]);
            max_val = max(max_val, a[i]);
            min_val = min(min_val, a[i]);
        }
    }
    return max_prod3;
}

C++ solution

int product3highest(const int values[], size_t count) {
  int highest[3] = { INT_MIN, INT_MIN, INT_MIN }; // keep sorted ascending
  while (count--) {
    if (values[count] > highest[0]) { // First check against lower value in highest[].
      if (values[count] >= highest[2]) {
        highest[0] = highest[1];
        highest[1] = highest[2];
        highest[2] = values[count];
      } else if (values[count] >= highest[1]) {
        highest[0] = highest[1];
        highest[1] = values[count];
      } else {
        highest[0] = values[count];
      }
    }
  }
  return highest[0] * highest[1] * highest[2];
}

For all positive elements in the array:

def prodThreeLargest(arr):
    max1 = max2 = max3 = float('-inf')
    for i in range(len(arr)):
        if arr[i] > max1:
            max3 = max2
            max2 = max1
            max1 = arr[i]
        elif arr[i] > max2:
            max3 = max2
            max2 = arr[i]
        elif arr[i] > max3:
            max3 = arr[i]
    #print("max1 {} max2 {} max3 {}".format(max1, max2, max3))

    return max1*max2*max3

For positive and negative elements:

import heapq


def prodThreeLargest(arr):
    n1, n2 = heapq.nsmallest(2, arr)
    print(n1, n2)
    p1, p2, p3 = heapq.nlargest(3, arr)
    print(p1, p2, p3)

    return max(n1*n2*p1, p1*p2*p3)

Isn't is just a two lines thing ...?

nums.sort()
return max(nums[-1] * nums[-2] * nums[-3], nums[-1] * nums[0] * nums[1])