Categories
interview

Find the maximum product of 3 integers in a list

The following code handles negatives as well.

Time Complexity O(n)
Space Complexity O(1)

Code

package algos;

public class maxThreeProd {
	public static int maxThree(int[] input) {
		if (input.length <= 3) {
			int ret = 1;
			for (int i = 0; i < input.length; i++) {
				ret *= input[i];
			}
			return ret;
		}

		int m1 = Integer.MIN_VALUE;
		int m2 = Integer.MIN_VALUE;
		int m3 = Integer.MIN_VALUE;
		int l1 = Integer.MAX_VALUE;
		int l2 = Integer.MAX_VALUE;
		for (int i = 0; i < input.length; i++) { if (input[i] > m1) {
				m3 = m2;
				m2 = m1;
				m1 = input[i];
			} else if (input[i] > m2) {
				m3 = m2;
				m2 = input[i];
			} else if (input[i] > m3) {
				m3 = input[i];
			}

			if (input[i] < l1) {
				l2 = l1;
				l1 = input[i];
			} else if (input[i] < l2) {
				l2 = input[i];
			}
		}

		return Math.max(l1 * l2 * m3, m1 * m2 * m3);

	}

	public static void main(String[] args) {
		int[] input = { 1, 5, 3, 2 };
		if (input.length == 0)
			System.out.println("null");
		else
			System.out.println(maxThree(input));
	}
}

Output

30