702948. Maximum product of two numbers
Basic
Maximum product of two numbers
Slug: maximum-product-of-two-numbers2730
Difficulty: Basic
Topic Tags: Arrays, Sorting, Algorithms, Greedy
Company Tags: Amazon, Samsung
Summary
Find the maximum product of two numbers in an array. The input contains only positive integers.
Detailed Explanation
To solve this problem, we can iterate through the array and keep track of the two largest numbers. We also need to consider the case where one number is 0 or negative because multiplying by 0 or a negative number will result in the maximum product being obtained with these numbers. Here's a step-by-step breakdown of the solution:
- Initialize
max1andmax2to store the two largest numbers. - Iterate through the array, updating
max1andmax2as needed. - If we encounter a number that is 0 or negative, swap it with
max2. This is because multiplying by 0 or a negative number will result in the maximum product being obtained with this number. - Finally, return the product of
max1andmax2.
Time complexity: O(n), where n is the size of the array.
Space complexity: O(1), as we only use a constant amount of space to store max1, max2, and a few other variables.
Optimized Solutions
#### Java
public int maxProduct(int[] nums) {
if (nums.length == 0) return 0;
int max1 = Integer.MIN_VALUE;
int max2 = Integer.MIN_VALUE;
for (int num : nums) {
if (num > max1) {
max2 = max1;
max1 = num;
} else if (num > max2) {
max2 = num;
}
if (max1 < 0) {
int temp = max1;
max1 = Math.max(max2, 0);
max2 = temp;
}
}
return max1 * max2;
}