Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!
  • Go

Idiom #218 List intersection

Create the list c containing all unique elements that are contained in both lists a and b.
c should not contain any duplicates, even if a and b do.
The order of c doesn't matter.

seta := make(map[T]bool, len(a))
for _, x := range a {
	seta[x] = true
}
setb := make(map[T]bool, len(a))
for _, y := range b {
	setb[y] = true
}

var c []T
for x := range seta {
	if setb[x] {
		c = append(c, x)
	}
}

Convert to sets, then iterate in one pass.
The runtime cost is O(n).
Elements have type T.
The final order is indeterminate.
func intersection[S ~[]T, T comparable](a, b S) S {
	s, l := a, b
	if len(b) < len(a) {
		s, l = b, a
	}

	set := make(map[T]struct{}, len(s))
	for _, x := range s {
		set[x] = struct{}{}
	}

	c := make(S, 0, len(s))
	for _, x := range l {
		if _, found := set[x]; found {
			c = append(c, x)
			delete(set, x)
		}
	}
	return c
}

Convert the smallest slices to a set, then iterate on the other slice to see which elements are also in the set.
Duplicate elements are ignored.
The final order is indeterminate.
Works for any comparable type T.


Complexity: O(N) [N = len(a)+len(b)]
Memory: O(N) [N = min(len(a), len(b)]
func intersection[S ~[]T, T comparable](a, b S) S {
	seta := make(map[T]bool, len(a))
	for _, x := range a {
		seta[x] = true
	}
	setb := make(map[T]bool, len(b))
	for _, y := range b {
		setb[y] = true
	}

	var c S
	for x := range seta {
		if setb[x] {
			c = append(c, x)
		}
	}
	return c
}

Convert to sets, then iterate in one pass.
The runtime cost is O(n).
The final order is indeterminate.
Works for any type parameter T.
(def c (clojure.set/intersection (set a) (set b)))
New implementation...
< > ⌨
programming-idioms.org 
seta := make(map[T]bool, len(a))
for _, x := range a {
	seta[x] = true
}
setb := make(map[T]bool, len(a))
for _, y := range b {
	setb[y] = true
}

var c []T
for x := range seta {
	if setb[x] {
		c = append(c, x)
	}
}
func intersection[S ~[]T, T comparable](a, b S) S {
	s, l := a, b
	if len(b) < len(a) {
		s, l = b, a
	}

	set := make(map[T]struct{}, len(s))
	for _, x := range s {
		set[x] = struct{}{}
	}

	c := make(S, 0, len(s))
	for _, x := range l {
		if _, found := set[x]; found {
			c = append(c, x)
			delete(set, x)
		}
	}
	return c
}
func intersection[S ~[]T, T comparable](a, b S) S {
	seta := make(map[T]bool, len(a))
	for _, x := range a {
		seta[x] = true
	}
	setb := make(map[T]bool, len(b))
	for _, y := range b {
		setb[y] = true
	}

	var c S
	for x := range seta {
		if setb[x] {
			c = append(c, x)
		}
	}
	return c
}
(def c (clojure.set/intersection (set a) (set b)))
c = a.Intersect(b).ToList();
C = lists:flatten([A -- B] ++ [B -- A]).
a `intersect` b
const c = [...new Set(a)].filter(e => b.includes(e));
Set<T> A = copyOf(a), B = copyOf(b);
List<T> c = A.stream().filter(B::contains).toList();
a.retainAll(b);
List<T> c = new ArrayList<>(copyOf(a));
a.retainAll(b);
List<T> c = List.copyOf(Set.copyOf(a));
Set<T> A = copyOf(a), B = copyOf(b);
List<T> c = new ArrayList<>();
for (T t : A) if (B.contains(t)) c.add(t);
$c = array_intersect($a, $b)
for elem in a do
  if (b.indexof(elem) >= 0) and (c.indexof(elem) = -1) then
    c.add(elem);
my %u;
$u{$_} = 1 for @a, @b;
my @c = keys %u;
c = list(set(a) & set(b))
c = list(set(a).intersection(b))
c = [*{*a} & {*b}]
c = a & b
let set_a: HashSet<_> = a.into_iter().collect();
let set_b: HashSet<_> = b.into_iter().collect();
let c = set_a.intersection(&set_b);
let unique_a = a.iter().collect::<HashSet<_>>();
let unique_b = b.iter().collect::<HashSet<_>>();

let c = unique_a.intersection(&unique_b).collect::<Vec<_>>();