go4fun.fun
Go4Fun - Fun Interview Puzzles

Follow

Go4Fun - Fun Interview Puzzles

Follow
Rust Interview Puzzles: Check if a slice with 0 sum exists in a vector

Rust Interview Puzzles: Check if a slice with 0 sum exists in a vector

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

2 min read

Problem

We need to check if an unsorted vector of numbers vec contains a contiguous sub-vector (slice) of 0 sum.

Example 1:

Input: vec = [4, 2, -3, 1, 6]
Output: true
Explanation: Because it contains a contiguous sub-vector [2, -3, 1].

Example 2:

Input: vec = [4, 2, 0, 1, 6]
Output: true
Explanation: Because it contains [0].

Example 3:

Input: vec = [-3, 2, 3, 1, 6]
Output: false
Explanation: Though it contains a sub-vector [-3, 3], but it's not contiguous.

Solution

fn check_if_slice_with_0_exists(vec: &Vec<i32>) -> bool {
    let mut set = HashSet::from([0]);
    let mut sum = 0;
    for e in vec {
        sum = sum + e;
        if set.contains(&sum) {
            return true;
        } else {
            set.insert(sum);
        }
    }
    return false;
}

Explanation

We iterate over the vector vec, accumulating sum of the vector values e along the way. And on each iteration we check if the current sum of the elements is in the HashSet set we created earlier. If the sum is not yet in the set, then we just add it to the set. If it is in the set, then we immediately return true as a result. The idea here is that if we encounter again a sum value that we've seen already before (the value that is already in the set), it means that after we saw that sum value for the first time, further elements added to the sum negated that original sum value, so that we encountered the same value again. That is only possible if the vector contains a contiguous sub-vector with 0 sum.

Complexity

The time complexity of this solution is O(n) (n is a size of the input vector). Also the solution requires O(n) extra space for the HashSet we created.


Rust Playground with this code

 
Share this