Find values present in both Python lists, in the first list's order, without duplicates. See why a set lookup turns O(n×m) into O(n+m).
The problem
Return the values that appear in both lists, in the order they appear in list1, each value once.
Examples
Example 1
Input
intersection([1, 2, 3, 4, 5], [4, 5, 6, 7, 8])
Expected output
[4, 5]
Example 2
Input
intersection([3, 1, 3, 2], [2, 3])
Expected output
[3, 2]
+ 3 hidden tests on Submit — nothing shared, dedupe output.
Edge cases to ask about
- Empty input
- No overlap
- Duplicates in either list
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| `x in list2` per element | O(n × m) | O(1) | Every lookup scans list2. |
| bestConvert list2 to a set | O(n + m) | O(m) | One pass to build the set, O(1) lookups after that. |
Walkthrough of the optimal approach (try it yourself first)
The brute force asks x in list2 for every x, and each of those questions scans list2 — O(n × m).
Build set(list2) once and each lookup becomes O(1) on average, so the whole thing is O(n + m). This is the "list lookup → set" optimisation interviewers expect you to spot.
set(list1) & set(list2) is shorter but loses the order of list1.
Complexity: O(n + m) time, O(m) space. Building the set from list2 is O(m); scanning list1 with O(1) lookups is O(n). Memory is the set of list2.
Reveal the reference solution
def intersection(list1, list2): other = set(list2) seen = set() out = [] for x in list1: if x in other and x not in seen: seen.add(x) out.append(x) return out
The brute force, for comparison
def intersection(list1, list2): out = [] for x in list1: if x in list2 and x not in out: # two list scans per element out.append(x) return out
Follow-ups interviewers ask
- Keep duplicates: [1,1,2] ∩ [1,1] → [1,1] (multiset intersection).
- Both lists are sorted — can you do it in O(1) extra space?
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Intersection of Two Lists in Python?
The optimal solution runs in O(n + m) time and O(m) auxiliary space. Building the set from list2 is O(m); scanning list1 with O(1) lookups is O(n). Memory is the set of list2.
What is the brute-force approach, and how do you optimise it?
`x in list2` per element: O(n × m) time, O(1) space. Every lookup scans list2. Convert list2 to a set: O(n + m) time, O(m) space. One pass to build the set, O(1) lookups after that.
What follow-up questions do interviewers ask about Intersection of Two Lists?
Keep duplicates: [1,1,2] ∩ [1,1] → [1,1] (multiset intersection). Both lists are sorted — can you do it in O(1) extra space?