11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Is it acceptable to change the method's signature to max_prod_three(Integer[] A) ? \$\endgroup\$ – Spotted Oct 30 '15 at 7:21
  • \$\begingroup\$ The only difference I see in doing that is that our input array can have null elements. So not sure if that is desirable. But if you think changing it will make the method more cleaner, then sure. \$\endgroup\$ – Haider Oct 30 '15 at 7:31
  • \$\begingroup\$ And does a lot clearer solution but with a worse space/time complexity interests you ? \$\endgroup\$ – Spotted Oct 30 '15 at 7:40
  • \$\begingroup\$ No, I want to maintain the optimal space and time complexity. \$\endgroup\$ – Haider Oct 30 '15 at 8:12
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You should take the repeated value as well. For e.g, [9, 9 , 3 , 1] should return 9*9*3 = 243 \$\endgroup\$ – Haider Oct 30 '15 at 9:47
  • \$\begingroup\$ @Haider edited the code (changed < and > to <= and >= respectively). \$\endgroup\$ – Gentian Kasa Oct 30 '15 at 9:52
  • \$\begingroup\$ Your first solution seems correct. But for the second solution that only uses a single loop, what will happen when the length of the array is 4. Wouldn't one of the values be unassigned and remain either Integer.MIN_VALUE or Integer.MAX_VALUE. That could mess up the solution. \$\endgroup\$ – Haider Oct 30 '15 at 10:01
  • \$\begingroup\$ You're right, there was an else that shouldn't have been there. Edited the code \$\endgroup\$ – Gentian Kasa Oct 30 '15 at 10:03
  • \$\begingroup\$ I downvoted because I believed this could be solved without so much raw array manipulation. I've upvoted now because I don't think that's a valid reason for a downvote at all. \$\endgroup\$ – lealand Nov 1 '15 at 17:31
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The only work around in that situation would be to change the method return type to something like BigInteger and work with that. So I think it is safe to assume that the given values will not overflow. \$\endgroup\$ – Haider Oct 30 '15 at 8:21
  • \$\begingroup\$ @Haider Or you could return the maximum integer (i.e. saturated multiply). But like you said, it's probably assumed that there will be no overflow. \$\endgroup\$ – JS1 Oct 30 '15 at 8:24
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I partially agree with your conclusion. I agree with the "Correctness and clarity should come first" and with the "Performance should come later" part, but not with the "if at all" one. IMO one should definitely think about performance improvements (once the correctness and clarity has been taken care of). The \$ O(n log n) \$ is ok in the general case, when the number of items \$ k \$ is not known a priori (even though it can still be improved), but in this case, \$ k \$ is known and is small enough that it can be managed directly without losing readability. \$\endgroup\$ – Gentian Kasa Oct 30 '15 at 16:07
  • \$\begingroup\$ @GentianKasa Is your partial agreement 97% as Knuth suggests? The difference between ideolgy and engineering is that in engineering fast enough is fast enough...and profilers. \$\endgroup\$ – ben rudgers Oct 30 '15 at 17:11
  • \$\begingroup\$ My partial agreement somewhat involves both ideology and engineering. I can't see why going with a \$ O(n log n) \$ when there's a \$ O(n) \$ solution that is correct and readable enough. Obviously I wouldn't go for the small performance optimizations like when to use for instead of foreach unless it was strictly necessary, but I'd definitely go for performance optimizations that affect complexity. Obviously, every case is special and almost unique and the solution should be applied to the specific case. \$\endgroup\$ – Gentian Kasa Oct 30 '15 at 17:39
  • \$\begingroup\$ @GentianKasa I believe that efficiency should also include programmer and economic efficiency. I've amended my answer with an epilogue to better demonstrate why the tradeoff makes sense...i.e. six lines of rather readable code versus several dozen. \$\endgroup\$ – ben rudgers Oct 30 '15 at 20:41
  • \$\begingroup\$ in that case it just means that we are talking about two different types of efficiency :) \$\endgroup\$ – Gentian Kasa Oct 31 '15 at 8:55
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I agree with your idea of using a min-max heap for the generalized case. But your solution will not work if you have negative numbers in the array. I believe you will need a max heap and a min heap of lengths n. Then you will have to use some sort of greedy approach to get the max product. \$\endgroup\$ – Haider Oct 31 '15 at 20:44
  • \$\begingroup\$ @Haider oooh great point. For some reason I was just thinking about positive integers. I'll come up with a better approach to catch that. \$\endgroup\$ – lealand Oct 31 '15 at 21:48
  • \$\begingroup\$ @Haider do you have test cases? \$\endgroup\$ – lealand Oct 31 '15 at 22:23
  • \$\begingroup\$ Isn't this a little too much for a relatively simple problem such as this? Wouldn't it be better to just sort the array as @benrudgers suggested and work on it in the general case? I mean, it's true that you'd have a \$O(n log n)\$ time complexity instead of \$O(n log k)\$ and a \$O(log n)\$ space complexity (assuming quicksort is used) instead of \$O(log k)\$ but the benefits you, as a developer, gain (development time, code complexity, code readability, just to name a few) far surpass the benefits you gain in terms of complexity. \$\endgroup\$ – Gentian Kasa Nov 1 '15 at 10:26
  • \$\begingroup\$ @GentianKasa I would absolutely use benrudgers solution if this problem was ever posed to me. I wouldn't even care about the time complexity if the solution was readable and maintainable. But the sensible answers to this question has already been posted; I've provided an additional, and admittedly inferior, solution but which hopefully meets the OP's time and space complexity requirements. I believe my original solution was quite elegant, but failed to handle negative integers. This is a problem where the complexity appears to explode in the general case. \$\endgroup\$ – lealand Nov 1 '15 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.