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.