Maximum product of a triplet in array in linear time

Given an array of integers, find the highest product you can get from three of the integers.

Input: [1, -4, 3, -6, 7, 0]

Output: 168

I would love to hear from how this might be refactored/improved.

GitHub

public static int highestProduct(int[] numbers) {
int largest, secondLargest, thirdLargest;
int smallest, secondSmallest;

largest = secondLargest = thirdLargest = Integer.MIN_VALUE;
smallest = secondSmallest = Integer.MAX_VALUE;

for (int number : numbers) {

// logic to find the largest numbers
if (number > largest) {
thirdLargest = secondLargest;
secondLargest = largest;
largest = number;
} else if (number > secondLargest) {
thirdLargest = secondLargest;
secondLargest = number;
} else if (number > thirdLargest) {
thirdLargest = number;
}

// logic to find the smallest numbers
if (number < smallest) {
secondSmallest = smallest;
smallest = number;
} else if (number < secondSmallest) {
secondSmallest = number;
}
}

return Math.max(largest * secondLargest * thirdLargest,
largest * smallest * secondSmallest);
}

@Rule
public ExpectedException thrown = ExpectedException.none();

@Test
public void invalidInput() {
thrown.expect(InvalidArgumentException.class);
HighestProductOfThree.highestProduct(new int[]{1, 2});
}

@Test
public void allPositiveNumbers() {
Assert.assertEquals(30000, HighestProductOfThree.highestProduct(new int[]{1, 3, 2, 100, 100}));
Assert.assertEquals(40, HighestProductOfThree.highestProduct(new int[]{1, 2, 4, 5}));
}

@Test
public void allNegativeNumbers() {
Assert.assertEquals(-30, HighestProductOfThree.highestProduct(new int[]{-20, -10, -5, -3, -2}));
}

@Test
public void mixedNumbers() {
Assert.assertEquals(300, HighestProductOfThree.highestProduct(new int[]{-10, -10, 1, 3, 2}));
Assert.assertEquals(168, HighestProductOfThree.highestProduct(new int[]{1, -4, 3, -6, 7, 0}));
}

• What about overflow handling? Input [Integer.MIN_VALUE, Integer.MIN_VALUE-1, Integer.MIN_VALUE-2, -1, 0, 1] – Johnbot Apr 7 '18 at 12:23
• That should be Integer.MIN_VALUE + 1 and Integer.MIN_VALUE + 2 not minus. – Johnbot Apr 7 '18 at 12:33
• This looks like Java and should be tagged as such. A source for the question would be nice too. Having the tag for challenge and interview seems redundant. – yuri Apr 7 '18 at 13:37

Your code is straightforward and easy to read. It also doesn't do anything unnecessary. You chose the variable names perfectly, got the indentation correct and provided good test cases. Since you mentioned in the title that there code needs to run in linear time, it is perfect.

I don't see where you throw the exception to make the first of your tests succeed. I bet that test fails currently. That test also imports InvalidArgumentException from a strange package instead of using the standard IllegalArgumentException. Are you coming from a .NET background?

Your code is rather long. If you prefer maintainability and readability over a few nanoseconds of execution time (complexity $\mathcal O(n\log n)$), you should rather write:

int[] nums = numbers.clone();
Arrays.sort(nums);

int n = nums.length;
return Math.max(
nums[n - 3] * nums[n - 2] * nums[n - 1],
nums[0] * nums[1] * nums[n - 1]);

• All test passes in my workspace. Oh no, I pasted the code without argument validation :-( Dont think I can update now as it code violate SO policy. – Exploring Apr 7 '18 at 10:19