Closed congr closed 5 years ago
NLogN
class Solution {
public int maximumProduct(int[] nums) {
Arrays.sort(nums);
int N = nums.length - 1;
int a = nums[0] * nums[1] * nums[N];
int b = nums[N] * nums[N-1] * nums[N-2];
return Math.max (a, b);
}
}
O(N)
class Solution {
public int maximumProduct(int[] nums) {
int min1 = Integer.MAX_VALUE, min2 = min1;
int max1 = Integer.MIN_VALUE, max2 = max1, max3 = max1;
for (int n : nums) {
// find 2 smallest numbers
if (n < min1) {
min2 = min1; // min1 : smallest
min1 = n;
} else if (n < min2) {
min2 = n;
}
// find 3 largest numbers
if (n > max3) { // max3 : largest
max1 = max2;
max2 = max3;
max3 = n;
} else if (n > max2) {
max1 = max2;
max2 = n;
} else if (n > max1) {
max1 = n;
}
}
int a = min1 * min2 * max3;
int b = max1 * max2 * max3;
return Math.max (a, b);
}
}
https://leetcode.com/problems/maximum-product-of-three-numbers/