Intersection and union
- Algorithms course
- Beginner
- Lesson 75/80
- 4 min
Compute the intersection and union of two sets.
Intersection implementation
To implement intersection, you take each element of one set and check if it is in the other. You add the ones that are to the result set.
This takes O(n) time (n = smaller set's size). Since each contains is O(1), the total is O(n).
Union implementation
To implement union, you add all elements from both sets to a new set. Duplicates are automatically eliminated.
This takes O(n + m) time (n and m are the sizes of the two sets). Since each add is O(1), the total is linear.
Practice Intersection
Write set_intersect(a, b). Return sorted intersection of a and b. Print [2, 3] with print(set_intersect({1,2,3}, {2,3,4})).
Starter code
def set_intersect(a, b):
# IntersectionSample solution
def set_intersect(a, b):
# Intersection
result = set()
for x in a:
if x in b:
result.add(x)
return sorted(result)
print(set_intersect({1, 2, 3}, {2, 3, 4}))Expected output
[2, 3]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Intersection and union: match the terms
| Term | Meaning |
|---|---|
intersection |
In both |
union |
In at least one |
O(n) |
Intersection |
O(n+m) |
Union |
2 Which elements does intersection give?
- Every element from both
- In both sets Correct answer
- Only in A
- Only in B
Explanation: Elements in both sets.
3 Union
Union adds ____ from both sets.Union adds all elements from both sets.Explanation: all elements is right.