use std::collections::HashSet;
use std::hash::Hash;
/// Finds the unique intersection of two slices/vectors (values that exist in both).
///
/// Accepts references (`&[T]`) to avoid taking ownership of input vectors.
/// Requires elements to implement `Eq`, `Hash`, and `Clone`.
///
/// # Complexity
/// - Time: O(n + m) where n and m are the lengths of the slices.
/// - Space: O(min(n, m)) auxiliary memory for the lookup set.
pub fn find_intersection<T>(first: &[T], second: &[T]) -> Vec<T>
where
T: Eq + Hash + Clone,
{
// Optimization: Build lookup set from the smaller slice to minimize memory footprint
if first.len() > second.len() {
return find_intersection(second, first);
}
// Load first slice into a HashSet for O(1) membership lookups
let mut lookup: HashSet<&T> = first.iter().collect();
// Pre-allocate vector capacity to prevent heap re-allocations
let mut result = Vec::with_capacity(lookup.len());
for item in second {
// HashSet::take removes the reference if present, automatically preventing duplicate matches
if lookup.take(item).is_some() {
result.push(item.clone());
}
}
result
}
fn main() {
let vec1 = vec![5, 7, 1, 1, 3, 0, 6, 2];
let vec2 = vec![2, 8, 8, 6, 9, 3, 3, 4, 4];
let intersection = find_intersection(&vec1, &vec2);
println!("vec1: {:?}", vec1);
println!("vec2: {:?}", vec2);
println!("Intersection: {:?}", intersection); // Output: [2, 6, 3]
}
/*
run:
vec1: [5, 7, 1, 1, 3, 0, 6, 2]
vec2: [2, 8, 8, 6, 9, 3, 3, 4, 4]
Intersection: [2, 6, 3]
*/
