Intersection and union

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.

Exercise 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})).

Show example 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}))

Test yourself

Intersection and union: match the terms

intersection

In both
union

In at least one
O(n)

Intersection
O(n+m)

Union
Which elements does intersection give?
- Every element from both
- In both sets
- Only in A
- Only in B
Show answer

In both sets — Elements in both sets.

Union

Union adds ____ from both sets.

Show answer

Union adds all elements from both sets.

Next lesson: Summary - Set

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies