go4fun.fun
Go4Fun - Fun Interview Puzzles

Follow

Go4Fun - Fun Interview Puzzles

Follow
Rust Interview Puzzles: Find a maximum product of 2 numbers in a vector

Rust Interview Puzzles: Find a maximum product of 2 numbers in a vector

go4fun.fun's photo
go4fun.fun
·Nov 29, 2022·

2 min read

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).


Rust Playground with this code

 
Share this