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

### 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`

.