Find out the 2 numbers which gives the highest product

Question

Input given is an int array, which may or may not contain positive, negative or zero values. Write a program to find out the two numbers which gives the highest product. (Both numbers should be positive or negative.)

Below is my code whose time complexity is O(n2), I believe. Is there any improvement I can make to the code?

public class FindLargestProduct{

    public static void main(String[] args) {
        int[] arr = { 52, 12, 34, 10, 6, 40, 0, 12, 40, 52, -56, -78, -99, 68 };
        int firstMax = 0, secondMax = 0;
        int firstNegMax = 0, secondNegMax = 0;

        for (int i = 0; i < arr.length; ++i) {

            if (arr[i] > 0) {
                if (arr[i] > firstMax) {
                    secondMax = firstMax;
                    firstMax = arr[i];
                } else if (arr[i] > secondMax) {
                    secondMax = arr[i];
                }
            }

            if (arr[i] < 0) {
                secondNegMax = firstNegMax;
                firstNegMax = arr[i];
                if (arr[i] > firstNegMax) {
                    secondNegMax = firstNegMax;
                    firstMax = arr[i];
                } else if (arr[i] > secondNegMax) {
                    secondNegMax = arr[i];
                }

            }
        }

        int proPositive = firstMax * secondMax;
        int proNegative = firstNegMax * secondNegMax;

        if (proPositive > proNegative) {
            System.out.println(proPositive);
        } else {
            System.out.println(proNegative);
        }
    }
}

Answer 1

Bugs

Your negative cases are wrong.

        if (arr[i] < 0) {
            secondNegMax = firstNegMax;
            firstNegMax = arr[i];

Here you always overwrite the current maximums...

            if (arr[i] > firstNegMax) {
                secondNegMax = firstNegMax;
                firstMax = arr[i];
            } else if (arr[i] > secondNegMax) {
                secondNegMax = arr[i];
            }

And here you check if a certain value is HIGHER than the max (which is negative, so 0 is higher than all negatives!). Neither of this is going to result in a good end result.

Aside from that, there seems to be no explicit check for verifying that you have at least an array of length 2 and that the output consists of either "two positive numbers" or "two negative numbers". Other than that, it's working fine.

Algorithm

I've got only one algorithmic improvement, and that's this one...

        if (arr[i] > 0) {
            if (arr[i] > firstMax) {
                secondMax = firstMax;
                firstMax = arr[i];
            } else if (arr[i] > secondMax) {
                secondMax = arr[i];
            }
        }

        if (arr[i] < 0) {
            secondNegMax = firstNegMax;
            firstNegMax = arr[i];
            if (arr[i] > firstNegMax) {
                secondNegMax = firstNegMax;
                firstMax = arr[i];
            } else if (arr[i] > secondNegMax) {
                secondNegMax = arr[i];
            }

        }

Here, you first check if the current element is positive... and then, later, you check if it's negative. Now, there's nothing wrong with that, but if you know that this element is positive, then there is no need for the negative check anymore. Use else-if here.

Naming

Your shorthand should be expanded, firstNegativeMax reads better than firstNegMax. max is well understood as "maximum", neg isn't as well understood. Aside from that, assigning arr[i] to a local variable with a name like "currentNumber" or "currentElement" would help readability. (Better yet, follow Martin R's advice and make it a for-each loop.)

Answer 2

More bugs

In addition to the bugs already mentioned by others, here are two more:

1. If an array consists of just one positive and one negative number, such as { 5, -2 }, your function will return zero instead of -10.

2. If the array contains large integers, your product will overflow when you multiply. You should use long variables instead of int to do your multiplications, and your function should return a long.

Answer 3

The actual computation should be done in a separate function, not in main():

public class FindLargestProduct{

    public static void main(String[] args) {

        int[] arr = { 52, 12, 34, 10, 6, 40, 0, 12, 40, 52, -56, -78, -99, 68 };
        int result = largestProduct(arr);
        System.out.println(result);
    }

    static int largestProduct(int[] array) {
        // ...         
    }
}

That increases the clarity of the program, and allows you to add unit tests easily.

Iteration over all array elements can be done with a "for-each loop", that saves the repeated array indexing and makes the code better readable:

for (int element : array) {

    if (element > 0) {
        if (element > firstMax) {
            secondMax = firstMax;
            firstMax = element;
        } else if (element > secondMax) {
            secondMax = element;
        }
    } 
    // ... and so on ...
}

You can also use

Math.max(proPositive, proNegative)

instead of a if-else-statement to determine the larger of the products.

Answer 4

Since many people already proposed improvements to your code snippet, I will address only one issue: readability.

The point is that you can make your method easier to follow without compromising its time complexity:

public static IntPairResult findLargestProduct(final int... array) {
    Objects.requireNonNull(array, "The input array is null.");

    if (array.length < 2) {
        throw new IllegalArgumentException(
                "The input array is too small (" + array.length + "). " +
                "Must have a length at least 2.");
    }

    if (array.length == 2) {
        return new IntPairResult(array[0], array[1]);
    }

    // Find the minimum and maximum elements in the array:
    int min = array[0];
    int max = array[0];
    int minIndex = 0;
    int maxIndex = 0;

    for (int i = 1; i < array.length; ++i) {
        final int current = array[i];

        if (min > current) {
            min = current;
            minIndex = i;
        } else if (max < current) {
            max = current;
            maxIndex = i;
        }
    }

    // Find the second largest and smallest elements in the array:
    int min2 = Integer.MAX_VALUE;
    int max2 = Integer.MIN_VALUE;

    for (int i = 0; i < array.length; ++i) {
        if (i == minIndex || i == maxIndex) {
            // Omit the actual minimum and maximum elements:
            continue;
        }

        final int current = array[i];

        if (min2 > current) {
            min2 = current;
        } else if (max2 < current) {
            max2 = current;
        }
    }

    final IntPairResult result1 = new IntPairResult(max, max2);
    final IntPairResult result2 = new IntPairResult(min, min2);

    return result1.getProduct() > result2.getProduct() ?
            result1 :
            result2;
}

where IntPairResult is as follows:

public class IntPairResult {

    private final int int1;
    private final int int2;

    public IntPairResult(final int int1, final int int2) {
        this.int1 = int1;
        this.int2 = int2;
    }

    public int getProduct() {
        return int1 * int2;
    }

    @Override
    public String toString() {
        return "[" + int1 + " * " + int2 + " = " + getProduct() + "]";
    }
}

Hope that helps.

Answer 5

Why reinvent the wheel? You want a sorted array, so just sort the array:

import java.util.Arrays;

public class FindLargestProduct
{
    public static void main(String[] args) 
    {
        int[] arr = { 52, 12, 34, 10, 6, 40, 0, 12, 40, 52, -56, -78, -99, 68 };

        Arrays.sort(arr);

        System.out.println(Math.max(arr[0]*arr[1], arr[arr.length-1]*arr[arr.length-2]));
    }
}

Answer 6

It looks like you're doing a lot of work to find the two largest and two smallest numbers in the array. There is an easy way to offload that work to the standard library: just call Array.Sort on your input array. Then your two lowest numbers will be at index 0 and 1, and your two largest will be at index length - 1 and length - 2. That way you can condense your loops down to like 4 lines of code. It takes your runtime from \$\mathcal{O}(n)\$ to \$\mathcal{O}(n \log n)\$ (I think the default array sort is \$\mathcal{O}(n \log n)\$), someone correct me if I'm wrong), but your implementation will look much more elegant and be easier to understand.