leetcode/java/628_Maximum_Product_of_Three_Numbers.java at master · jakehoare/leetcode · GitHub

43 lines (37 loc) · 1.19 KB

https://leetcode.com/problems/maximum-product-of-three-numbers/

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Solution can only be the product of the 3 largest numbers, or the largest and the 2 smallest.

Iterate over array, updating the 3 largest and 2 smallest numbers seen.

Alternatively, sort the array.

Time - O(n)

Space - O(1)

class Solution {

public int maximumProduct(int[] nums) {

int max1 = Integer.MIN_VALUE;

int max2 = Integer.MIN_VALUE;

int max3 = Integer.MIN_VALUE;

int min1 = Integer.MAX_VALUE;

int min2 = Integer.MAX_VALUE;

for (int num : nums) {

if (num > max1) {

max3 = max2;

max2 = max1;

max1 = num;

} else if (num > max2) {

max3 = max2;

max2 = num;

} else if (num > max3) {

max3 = num;

}

if (num < min1) {

min2 = min1;

min1 = num;

} else if (num < min2) {

min2 = num;

}

return Math.max(max1 * max2 * max3, max1 * min1 * min2);

}

Expand file tree