Follow

Follow

# Rust Interview Puzzles: Find pairs with a provided difference in a vector

go4fun.fun
·Dec 6, 2022·

### Problem

In a vector `vec` we need to find all pairs of the elements with a provided difference `diff`.

#### Example 1:

Input: `vec = [1, 5, 2, 2, 2, 5, 5, 4]`, `diff = 3`
Output: `[(1, 4), (2, 5)]`
Explanation: `(1, 4)` and `(2, 5)` pairs have the difference of the elements `3`.

#### Example 2:

Input: `vec = [1, 5, 6]`, `diff = 2`
Output: `[]`
Explanation: There are no pairs with the difference of the elements `2`.

### Solution

``````fn find_pairs_with_difference(vec: &Vec<i32>, diff: i32) -> Vec<(i32, i32)> {
let mut set = HashSet::new();

vec.iter().for_each(|e| {
set.insert(e);
});

vec.iter()
.flat_map(|&e| {
let another = e + diff;
if set.contains(&another) {
set.remove(&another);
Some((e, another))
} else {
None
}
})
.collect()
}
``````

### Explanation

One easy way to solve this puzzle in linear time is using an auxiliary `HashSet` data structure. First, we iterate over the vector `vec` and add all elements to the `set`. And then we iterate over the vector `vec` again and for each element `e` check if a corresponding `another` element (`e + diff`) exists in the `set`. If that is the case, then have found the counterpart for `e` and we wrap the pair as `Some((e, another))`. If not, then we return `None` for the current element. Since we use `flat_map`, our found pairs would be automatically unwrapped from `Some`, while `None` results would be discarded. Also note that when we have found a pair, we remove the corresponding element from the set `set.remove(&another)` - that is a way to avoid having duplicated pairs in the result (which would happen if the vector `vec` contains duplicates).

### Complexity

The time complexity of this solution is `O(n)` (`n` is a size of the input vector), even though we iterated over the vector `vec` twice. The auxiliary space complexity is `O(n)` since we used an additional `HashSet`.