Hey everyone! π
Today, we're solving a classic coding interview problem: Find Pairs with Target Sum.
The Problem
The goal is to write a function that finds all pairs of numbers in a list that add up to a specific target sum.
- The function should return a list of tuples.
- Each pair should appear only once (uniqueness).
- The order of elements in the tuple should be consistent (e.g., sorted).
Example:
-
find_pairs([1, 5, 7, -1, 5], 6)should return[(1, 5), (7, -1)] -
find_pairs([2, 3, 4, 5], 9)should return[(4, 5)]
The Solution
Here is the Python implementation:
def find_pairs(lst, target):
"""
Finds all unique pairs in the list that sum up to the target.
"""
seen = set()
pairs_found = set()
for num in lst:
complement = target - num
if complement in seen:
pairs_found.add((min(num, complement), max(num, complement)))
seen.add(num)
return list(pairs_found)
# Test cases
print(find_pairs([1, 5, 7, -1, 5], 6))
# Output: [(1, 5), (-1, 7)]
Code Breakdown
Let's walk through the code line by line:
-
def find_pairs(lst, target):- Defines a function named
find_pairsthat takes a list of numberslstand a target sumtarget.
- Defines a function named
-
seen = set()- Initializes an empty set called
seento keep track of numbers we have encountered so far. Sets are used for O(1) lookups.
- Initializes an empty set called
-
pairs_found = set()- Initializes a set called
pairs_foundto store the valid pairs. Using a set ensures that we don't store duplicate pairs (e.g., if the same pair appears multiple times in the list).
- Initializes a set called
-
for num in lst:- Iterates through each number
numin the input list.
- Iterates through each number
-
complement = target - num- Calculates the
complement. This is the number we need to find in ourseenset to make thetargetsum with the currentnum.
- Calculates the
-
if complement in seen:- Checks if the
complementexists in theseenset. If it does, it means we have found a pair (num+complement=target).
- Checks if the
-
pairs_found.add((min(num, complement), max(num, complement)))- If a pair is found, we add it to
pairs_found. -
min(num, complement), max(num, complement)creates a tuple where the smaller number comes first. This normalization ensures that(1, 5)and(5, 1)are treated as the same pair and handled correctly by the set's uniqueness property.
- If a pair is found, we add it to
-
seen.add(num)- Adds the current number
numto theseenset so it can be used as a complement for future numbers.
- Adds the current number
-
return list(pairs_found)- Converts the set of pairs back into a list and returns it.
Example Walkthrough
Let's trace the function with find_pairs([1, 5, 7, -1, 5], 6):
- Initialization:
seen = {},pairs_found = {},target = 6 - Iteration 1:
num = 1-
complement = 6 - 1 = 5 - Is
5inseen? No. - Add
1toseen:seen = {1}
-
- Iteration 2:
num = 5-
complement = 6 - 5 = 1 - Is
1inseen? Yes. - Add
(1, 5)topairs_found.pairs_found = {(1, 5)} - Add
5toseen:seen = {1, 5}
-
- Iteration 3:
num = 7-
complement = 6 - 7 = -1 - Is
-1inseen? No. - Add
7toseen:seen = {1, 5, 7}
-
- Iteration 4:
num = -1-
complement = 6 - (-1) = 7 - Is
7inseen? Yes. - Add
(-1, 7)topairs_found.pairs_found = {(1, 5), (-1, 7)} - Add
-1toseen:seen = {1, 5, 7, -1}
-
- Iteration 5:
num = 5-
complement = 6 - 5 = 1 - Is
1inseen? Yes. - Add
(1, 5)topairs_found.pairs_foundis a set, so it remains{(1, 5), (-1, 7)}. - Add
5toseen.
-
Final Result: [(1, 5), (-1, 7)] (Order in list may vary, but pairs are correct).
Happy coding! π»
Top comments (0)