Python Set intersection()

Python’s set.intersection(sets) creates and returns a new set consisting of the elements that are members of all sets — this and the set argument(s). The resulting set has at most as many elements as any other set given in the argument list.

Here’s a minimal example that creates a new set arising from the intersection of two sets s and t:

>>> s = {1, 2, 3, 4}
>>> t = {3, 4, 5}
>>> s.intersection(t)
{3, 4}

Syntax

Let’s dive into the formal syntax of the set.intersection() method.

set.intersection(*sets)

Return Value of Set intersection()

The return value of set.intersetion() is a new set consisting of the elements that are members of all sets, including the set it is called on. It has at most the number of elements as any other set involved in the intersection.

Advanced Examples Set Intersection

There are some subtleties you need to understand regarding the set intersection method. Let’s dive into them by example!

The straightforward example is to calculate the intersection of a set with one of its subsets. In this case, the result is the subset because all elements in the subset are already elements of the superset, by definition.

>>> {1, 2, 3}.intersection({1, 2})
{1, 2}

But what if you’d invert this and calculate the intersection of a subset and a superset? In this case, the result is the same as before:

>>> {1, 2}.intersection({1, 2, 3})
{1, 2}

Can you compute the intersection of a set and an empty set? Sure! The return value is the empty set

>>> {1, 2, 3}.intersection(set())
set()

What if there’s an overlap between both sets but both sets have elements that are not contained in the other one? In this case, you’d take only the elements in the overlap.

>>> {1, 2, 3}.intersection({2, 3, 4})
{2, 3}

Set Intersection Multiple Set Arguments

You can compute the intersection of an original set and an arbitrary number of set arguments. In this case, the return value will be a set that contains only elements that are members of all involved sets.

Here’s an example:

>>> {1, 2, 3, 4, 5, 6}.intersection({1, 2}, {1, 3, 4}, {1, 3, 5})
{1}

Only the element 1 is a member of all involved sets.

Python Set Intersection &

A much more concise way to write the set intersection is the overloaded operator &. When applied to two sets s and t, the result of s & t is the same as calling s.intersection(t). It computes the intersection of the sets.

Here’s a basic example:

>>> {1, 2, 3, 4}.intersection({3, 4, 5})
{3, 4}
>>> {1, 2, 3, 4} & {3, 4, 5}
{3, 4}

This & notation is more concise and readable. Therefore, you may want to choose the & operator over the set.intersection() method.

To compute the set intersection of multiple sets with the & operator, chain together multiple intersection computations like this: s0 & s1 & s2 & ... & sn.

>>> {1, 2, 3, 4, 5} & {1, 2} & {1, 2, 3} & {1, 3, 4, 2}
{1, 2}

You don’t need to import any library to use the & operator—it is built-in.

Set intersection() vs intersection_update()

The set.intersection() method returns a new set whereas the set.intersection_update() operates on the set it is called upon and returns None.

• s.intersection(t) – Creates a new set with the intersection of s and t. The original set s remains unchanged. Returns the new set.
• s.intersection_update(t) – Works on the original set s and removes all elements that are not in t. Returns None.

Here’s an example that shows the difference between both methods:

>>> s = {1, 2, 3}
>>> t = s.intersection({1, 2})
>>> s
{1, 2, 3}

And the set.intersection_update() updates on an existing set s and returns None:

>>> s = {1, 2, 3}
>>> s.intersection_update({1, 2})
>>> s
{1, 2}

What is the Time Complexity of Set Intersection in Python?

The runtime complexity of the set.intersection() method on a set with n elements and a set argument with m elements is O(min(n, m)) because you need to check for the smaller set whether each of its elements is a member of the larger set. Checking membership is O(1), so the runtime complexity is O(min(n, m)) * O(1) = O(min(n, m)).

You can see this in the following simple experiment where we run the set method multiple times for increasing set sizes:

I ran this experiment on my Acer Aspire 5 notebook (I know) with Intel Core i7 (8th Gen) processor and 16GB of memory. Here’s the code of the experiment:

import matplotlib.pyplot as plt
import time

sizes = [i * 10**5 for i in range(50)]
runtimes = []

for size in sizes:
    s = set(range(size))
    t = set(range(0, size, 2))

    # Start track time ...
    t1 = time.time()
    s.intersection(t)
    t2 = time.time()
    # ... end track time
    
    runtimes.append(t2-t1)


plt.plot(sizes, runtimes)
plt.ylabel('Runtime (s)')
plt.xlabel('Set Size')

plt.show()

Other Python Set Methods

All set methods are called on a given set. For example, if you created a set s = {1, 2, 3}, you’d call s.clear() to remove all elements of the set. We use the term “this set” to refer to the set on which the method is executed.