Maximum product of 3 integers in an int array

Question

I want to find the maximum product that can be obtained from any 3 integers in an integer array. The optimal solution has time complexity of \$O(n)\$ and space complexity of \$O(1)\$. I managed to write up as solution in Java that only traverses the array twice (so my time complexity is \$O(n)\$) and my space complexity is \$O(1)\$. I do not believe the solution can be any cleaner than this but would still like to see what other people think.

The \$O(n)\$ solution is obtained by keeping track of the max three integers and the min two integers. The max product will either be (min_one * min_two * max_one) or (max_one * max_two * max_three).

// Assume input array is of at least length 3.

public int max_prod_three(int[] A){

    int len = A.length;

    // Base case
    if (len == 3) return A[0]*A[1]*A[2];

    int max = A[0], min = A[0], max_index = 0, min_index = 0;

    for (int i = 0; i < len; i++) {

        if (A[i] > max) {

            max = A[i];
            max_index = i;
        }
        else if (A[i] < min) {

            min = A[i];
            min_index = i;
        }
    }

    int max_sec = min, max_third = min , min_sec = max;

    for (int i = 0; i < len; i++) {

        if (i == max_index || i == min_index) continue;

        if (A[i] > max_sec) {

            max_third = max_sec;
            max_sec = A[i];
        }
        else if (A[i] > max_third) {
            max_third = A[i];
        }

        if (A[i] < min_sec) min_sec = A[i];

    }

    int prod_one = max * max_sec * max_third ;
    int prod_two = min * min_sec * max ;

    if (prod_one > prod_two) return prod_one ;
    return prod_two;
}

You can iterate through the array only once and get the max product but I found that the solution gets a bit too messy (with a lot more if else statements). But if anyone can do it cleanly, I would like to know.

Answer 1

While the approach is clear, the implementation could be made a little more readable, in my opinion, by using two helper methods: int[] getMaxThree(int[] arr), which returns the greatest 3 numbers in decreasing order (from greatest to smallest), and int[] getMinTwo(int[] arr), which returns the smallest 2 numbers in increasing order (even though it's not strictly necessary). By doing so, the main method is reduced to:

public int max_prod_three(int[] A){
    int[] maxThree = getMaxThree(A);
    int[] minTwo = getMinTwo(A);

    return Math.max(maxThree[0] * maxThree[1] * maxThree[2], 
                    maxThree[0] * minTwo[0] * minTwo[1]);
}

The helper methods could be something like the following:

private int[] getMaxThree(int[] arr){
    int[] result = { Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE };
    int len = arr.length;

    for(int i = 0; i < len; i++){
        if(arr[i] >= result[0]){
            result[2] = result[1];
            result[1] = result[0];
            result[0] = arr[i];
        } else if(arr[i] >= result[1]){
            result[2] = result[1];
            result[1] = arr[i];
        } else if(arr[i] >= result[2]){
            result[2] = arr[i];
        }
    }

    return result;
}

private int[] getMinTwo(int[] arr){
    int[] result = { Integer.MAX_VALUE, Integer.MAX_VALUE };
    int len = arr.length;

    for(int i = 0; i < len; i++){
        if(arr[i] <= result[0]){
            result[1] = result[0];
            result[0] = arr[i];
        } else if(arr[i] <= result[1]){
            result[1] = arr[i];
        }
    }

    return result;
}

From a performance point of view it's better to do everything in a single for loop and do something like:

public int max_prod_three(int[] A){
    int maxOne = Integer.MIN_VALUE, 
        maxTwo = Integer.MIN_VALUE, 
        maxThree = Integer.MIN_VALUE, 
        minOne = Integer.MAX_VALUE, 
        minTwo = Integer.MAX_VALUE;
    int len = A.length;

    for(int i = 0; i < len; i++){
        if(A[i] >= maxOne){
            maxThree = maxTwo;
            maxTwo = maxOne;
            maxOne = A[i];
        } else if(A[i] >= maxTwo){
            maxThree = maxTwo;
            maxTwo = A[i];
        } else if(A[i] >= maxThree){
            maxThree = A[i];
        } 

        if(A[i] <= minOne){
            minTwo = minOne;
            minOne = A[i];
        } else if(A[i] <= minTwo){
            minTwo = A[i];
        }
    }

    return Math.max(maxOne * maxTwo * maxThree, 
                    maxOne * minOne * minTwo);
}

P.S: The code is not tested.

Answer 2

Minor edge case

It's possible that the product of three integers will overflow. For example, three positive integers may produce a negative product and cause your function to return the other product instead. Since your function returns an int, it's not clear what you are supposed to do if that happens. Perhaps you are guaranteed that the values are small enough not to overflow?

Otherwise the function looks correct and easy to understand.

Answer 3

Preface

This review treats the code as a professional exercise rather than an academic one.

Introduction

Your intuition about one pass versus two passes was spot on.

Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. -- Donald Knuth

You Ain't Gonna Need It

In most cases O(n log n) time complexity is highly likely to be good enough. Sorting the array first makes the logic simple.

Pseudo-Code

MyArray = Input.sort
End = MyArray.length - 1
Candidate0 = 0
Candidate1 = MyArray[End] * MyArray[0] * MyArray[1]
Candidate2 = MyArray[End] * MyArray[End - 1] * MyArray[End - 2]
Return Max(Candidate0, Candidate1, Candidate2)

Performance Concerns?

Use a profiler. It is highly unlikely that the critical performance bottleneck of an interesting piece of software is a routine running in O(n log n) time.

Take Advantage of the Platform

Making assumptions about the execution path of a Java program as if it is assembly or C is an error. The Java JIT does branch prediction with one eye on the branch predition, prefetch and cache strategies of the hardware CPU. Java's sort is tuned to the eyeballs. Many man hours have gone into optimizing it to work with the JVM's underlying optimization strategies.

Hand rolled code that branches randomly is likely to see less optimization and memory latency of cache misses could swamp the theoretical efficiency of O(n) versus O(n log n) even in a critical section. Use a profiler.

Conclusion

Your intuition was sound. Correctness and clarity should come first. Performance should come later, if at all, and then only when it actually matters. The intuition just wasn't pushed far enough.

Epilogue

If, as some programmers believe, bugs are proportional to lines of code and software maintenance is a substantial fraction of total software cost, then it stands to reason that more compact code will contain fewer bugs and cost less.

Often it is easier to read as well:

public int max_prod_three(int[] A){
    private int end = A.length;
    private int[] MySortedArray = A.sort();
    return Math.max(MySortedArray[0] * MySortedArray[1] * MySortedArray[end],
                    MySortedArray[end - 2] * MySortedArray[end - 1] * MySortedArray[end],
                    0);
}

Afterward

Programs must be written for people to read, and only incidentally for machines to execute. -- Ableson and Sussman

Answer 4

Minor tweak

    int max = A[0], min = A[0], max_index = 0, min_index = 0;

    for (int i = 0; i < len; i++) {

It's a trivial speed improvement, but you can just say

    int max = A[0], min = A[0], max_index = 0, min_index = 0;

    for (int i = 1; i < len; i++) {

Both comparisons will always be false when i is 0.

Handling overflow

    int prod_one = max * max_sec * max_third ;
    int prod_two = min * min_sec * max ;

    if (prod_one > prod_two) return prod_one ;
    return prod_two;

You don't have to make the products into BigInteger values to avoid overflowing the comparison in this case. The following code will be sufficient:

    int signum = Integer.signum(max);
    long prod_one = signum * max_sec * max_third;
    long prod_two = signum * min * min_sec;

    if (prod_one > prod_two) {
        return prod_one * (int)Math.abs(max);
    }

    return prod_two * (int)Math.abs(max);

Then you only have to worry that the product will overflow the return type. You will always return the correct product--you just might not return the correct value of that product.

This works because max is in both sides of the comparison. You can divide it out unless it is zero. But signum is zero if max is. So if max is zero, multiplying by signum does the same thing.

If max is negative or positive, you can divide out the absolute value of max from both sides. But when you do that, you get signum again.

So you always get the same result from this comparison as from the original comparison, assuming no overflow. And this product will never overflow. The product of two 31-bit integers will always fit into a 63-bit long. At most it will be \$-2^{31} * -2^{31} = 2^{62}\$, which is a 63-bit value.

Answer 5

The key to this problem is a min-max heap. To rephrase the question in a generalised case, given an integer \$n\$ and an integer array of length \$m\$, find the largest product from any \$n\$ integers in that array. The optimal solution is \$O(n + m)\$ time complexity, and \$O(m)\$ space complexity. In your question, substitute \$m = 3\$ and you have the same complexity class as originally stated, since \$m\$ is now constant.

Here's a Java 8 solution which I think is really clean, though I'm having troubles adding the initial array to the collection... It uses the Google Guava library for its MinMaxPriorityQueue:

The first solution is a recursive algorithm which handles any sort of integer. The idea is that we first partition all the integers into two different lists, depending on whether they're positive or negative. Once we've done this, we know that we have two sets of numbers (the positives and negatives), and we want to take any \$m\$ of them to create the largest product. If all the integers a positive, then the problem is simple: just multiply the first \$n\$ largest numbers of \$m\$.

However, if there are negative integers in the array, things become complicated. To reason this out, lets consider all the integers in \$m\$ as either being a positive set, or a negative set. If we want to find the largest positive integer that can be made from the product of \$m\$ of these integers, we'll do the following in a recursive iteration:

• Take the largest positive integer

• Compare it to the product of the next two smallest negative integers (the products being a positive values).

• Call the recursive function with the larger value.

• Handle the miscellaneous edge cases, of which are many!

Here's the code below:

public static long maxProduct(final int n, final int[] m) {
  if (0 > n || m.length < n) {
    throw new IllegalArgumentException(
        String.format("n must be non-negative and array m must have at least %d elements", n));
  }

  final Queue<Integer> positives = MinMaxPriorityQueue.<Integer>orderedBy(Comparator.reverseOrder()).create();
  final Queue<Integer> negatives = MinMaxPriorityQueue.<Integer>orderedBy(Comparator.naturalOrder()).create();

  Arrays.stream(m).forEach(i -> {
    if (0 > i) {
      negatives.add(i);
    } else {
      positives.add(i);
    }
  });

  return recursiveMaxProduct(n, positives, negatives);
}

private static long recursiveMaxProduct(final int n, final Queue<Integer> positives, final Queue<Integer> negatives) {
  return recursiveMaxProduct(1L, n, positives, negatives);
}

private static long recursiveMaxProduct(final long acc, final int n, final Queue<Integer> positives, final Queue<Integer> negatives) {
  if (0 == n || (positives.isEmpty() && negatives.isEmpty())) {
    return acc;
  }

  if (1 < negatives.size()) {
    final int firstNegative = negatives.remove();
    final int secondNegative = negatives.remove();
    final long product = firstNegative * secondNegative;

    if (positives.isEmpty()) {
      return recursiveMaxProduct(product, n - 1, positives, negatives);
    } else {
      final int positive = positives.remove();
      if (product > positive) {
        positives.add(positive);
        return recursiveMaxProduct(product, n - 2, positives, negatives);
      } else {
        negatives.add(firstNegative);
        negatives.add(secondNegative);
        return recursiveMaxProduct(positive, n - 1, positives, negatives);
      }
    }
  }

  if (positives.isEmpty()) {
    return recursiveMaxProduct(acc * negatives.remove(), n - 1, positives, negatives);
  } else {
    return recursiveMaxProduct(acc * positives.remove(), n - 1, positives, negatives);
  }

  return acc;
}