Rust Interview Puzzles: Find a maximum product of 2 numbers in a vector
Problem
We need to find a maximum product of 2 numbers in a provided vector of numbers vec
. In math, a product of 2 numbers is a result of multiplication of these 2 numbers.
Example 1:
Input: vec = [-10, -3, 5, 7, -2]
Output: 35
Explanation: A product of (5, 7)
is the max product.
Example 2:
Input: vec = [-10, -3, 5, 4, -2]
Output: 30
Explanation: A product of (-10, -3)
is the max product.
Example 3:
Input: vec = [-5, 0, 10]
Output: 0
Explanation: A product of (-5, 0)
or (0, 10)
is the max product.
Solution
fn find_max_product_of_2_numbers(vec: &Vec<i32>) -> i32 {
let mut max_pos_1 = 0;
let mut max_pos_2 = 0;
let mut min_neg_1 = 0;
let mut min_neg_2 = 0;
for e in vec {
if *e > 0 && *e > max_pos_1 {
max_pos_2 = max_pos_1;
max_pos_1 = *e;
} else if *e > 0 && *e > max_pos_2 {
max_pos_2 = *e;
}
if *e < 0 && *e < min_neg_1 {
min_neg_2 = min_neg_1;
min_neg_1 = *e;
} else if *e < 0 && *e < min_neg_2 {
min_neg_2 = *e;
}
}
let product_of_max_positives = max_pos_1 * max_pos_2;
let product_of_min_negatives = min_neg_1 * min_neg_2;
match (product_of_max_positives, product_of_min_negatives) {
(pos, neg) if pos != 0 && neg != 0 && pos >= neg => pos, //product of positives is larger
(pos, neg) if pos != 0 && neg != 0 && pos <= neg => neg, //product of negatives is larger
(pos, 0) if pos != 0 => pos, //has only a product of positives
(0, neg) if neg != 0 => neg, //has only a product of negatives
_ if max_pos_1 != 0 && min_neg_1 != 0 && vec.len() == 2 => max_pos_1 * min_neg_1, //has 1 pos & 1 neg number
_ => 0, //otherwise returns 0
}
}
Explanation
In general, a maximum product number would come from either multiplying 2 maximum positive numbers OR 2 minimum negative numbers. It means that we need to iterate once over the vector vec
to find these 4 numbers (max_pos_1
, max_pos_2
, min_neg_1
, min_neg_2
). Then we could find a product of 2 maximum positive numbers AND a product of 2 minimum negative numbers. A maximum value from these products would give us a maximum product overall.
Also we need to handle special cases when there are no positive (or negative) pairs in the vector vec
, or when the vector contains zeros.
Complexity
The time complexity of this solution is O(n)
(n
is a size of the input vector).