Find every unique pair in a Python list that adds up to a target using a hash set in O(n). Compare against the nested-loop O(n²) brute force.
The problem
Return every unique pair of values from nums whose sum equals target.
- Write each pair as a tuple
(smaller, larger). - A value can pair with itself only if it appears twice.
- The order of pairs in the list does not matter.
Examples
Example 1
Input
pairs_with_sum([2, 4, 3, 5, 7, 8, 9], 10)
Expected output
[(2, 8), (3, 7)]
Example 2
Input
pairs_with_sum([1, 1, 2, 3], 2)
Expected output
[(1, 1)]
+ 4 hidden tests on Submit — single 5 cannot pair with itself, same pair only once.
Edge cases to ask about
- Duplicates
- Value pairing with itself
- Negative numbers
- No pairs
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 |
|---|---|---|---|
| Nested loops | O(n²) | O(1) | Try every pair i < j. |
| Sort + two pointers | O(n log n) | O(1) | Move inward from both ends depending on the current sum. |
| bestHash set of complements | O(n) | O(n) | For each x, check whether target − x was already seen. |
Walkthrough of the optimal approach (try it yourself first)
Scan once. For each x, the partner it needs is target - x. If that partner is already in seen, record the pair as (min, max) in a set so repeats collapse. Then add x to seen.
Because the partner must have been seen earlier, a lone 5 never pairs with itself, but two 5s do.
Complexity: O(n) time, O(n) space. One pass, with O(1) average set lookups. The two sets can each grow to n entries.
Reveal the reference solution
def pairs_with_sum(nums, target): seen = set() pairs = set() for x in nums: y = target - x if y in seen: pairs.add((min(x, y), max(x, y))) seen.add(x) return sorted(pairs)
The brute force, for comparison
def pairs_with_sum(nums, target): out = set() for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: out.add((min(nums[i], nums[j]), max(nums[i], nums[j]))) return sorted(out)
Follow-ups interviewers ask
- Return index pairs instead of value pairs.
- What if the list is already sorted? (two pointers, O(1) space)
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Find All Pairs That Sum to a Target in Python?
The optimal solution runs in O(n) time and O(n) auxiliary space. One pass, with O(1) average set lookups. The two sets can each grow to n entries.
What is the brute-force approach, and how do you optimise it?
Nested loops: O(n²) time, O(1) space. Try every pair i < j. Sort + two pointers: O(n log n) time, O(1) space. Move inward from both ends depending on the current sum. Hash set of complements: O(n) time, O(n) space. For each x, check whether target − x was already seen.
What follow-up questions do interviewers ask about Find All Pairs That Sum to a Target?
Return index pairs instead of value pairs. What if the list is already sorted? (two pointers, O(1) space)