How to Solve the Two-Sum Problem in Python
The Two Sum Problem is a common challenge in coding interviews. It involves finding two numbers in a list that add up to a specific target.
As a seasoned developer passionate about writing efficient and elegant Python solutions, I'll guide you through solving this problem step by step.
We'll examine code examples, understand their functionality, and optimize them to ensure they are as efficient and clear as possible.
The Code
Here's the original implementation provided:
from typing import List
class Solution:
def second_index(self, i: int, other_val: int, nums: List[int]) -> int:
"""
Returns the index of `other_val` in the list `nums`.
If `other_val` appears more than once and the first occurrence
is at index ` i', it returns the *second* occurrence (after `i').
Args:
i (int): Current index of the first number.
other_val (int): The complement needed to reach the target.
nums (List[int]): The list of numbers.
Returns:
int: Index of the complement.
Example:
>>> sol = Solution()
>>> sol.second_index(0, 3, [3, 3, 4])
1
"""
if i == nums.index(other_val):
return nums.index(other_val, i + 1)
else:
return nums.index(other_val)
def twoSum(self, nums: List[int], target: int) -> List[int]:
"""
Returns indices of the two numbers in the list `nums` that add up to the `target`.
This version accounts for:
- Duplicate numbers (e.g., [3, 3] with target 6)
- One-pass search with built-in functions
Args:
nums (List[int]): The list of integers.
target (int): The target sum.
Returns:
List[int]: A list containing the two indices that add up to the target.
Example (Easy):
>>> sol = Solution()
>>> sol.twoSum([2, 7, 11, 15], 9)
[0, 1]
Example (With Duplicates - Medium):
>>> sol.twoSum([3, 3], 6)
[0, 1]
Example (Unordered List - Complex):
>>> sol.twoSum([1, 4, 2, 5, 11], 6[1, 4, 2, 5, 11])
[1, 2]
Example (Edge Case - No Match):
>>> sol.twoSum([1, 2, 3], 10)
[]
"""
for i in range(len(nums)):
other_val = target - nums[i]
if other_val in nums:
if other_val == nums[i] and nums.count(nums[i]) == 1:
continue
j = self.second_index(i, other_val, nums)
return [i, j]
return []
This code solves the Two Sum Problem but has room for optimization in terms of performance and readability.
Before diving into optimization, let's analyze the code.
How the Code Works
Step 1: The second_index Method
This method finds the second occurrence of a value in the list if it's needed:
If the index of the current element matches the index of the target value (other_val), it moves forward to search for another occurrence of other_val.
Otherwise, it simply returns the first index of other_val.
Step 2: The Two-Sum Method
- Loop through the array with i representing the index of the current number.
- For each number, calculate other_val (the value that needs to pair with the current number to equal the target).
- Check if other_val exists in the list:
- Skip if other_val is the same as the current number and appears only once in the list.
- Use second_index to find the correct index of other_val if there are duplicates.
- Return the indices of the two numbers (i and j) if a match is found.
Edge Case Handling
If no two numbers meet the condition, the function returns an empty list ([]).
Time Complexity and Challenges
Time Complexity
The .index() and .count() methods are used multiple times, each with O(n) complexity.
The overall complexity is approximately O(n²) in the worst case due to the nested operations.
Challenges
Using .index() repeatedly makes the solution inefficient for larger inputs.
The second_index method is unnecessarily complex.
This code could struggle with lists containing many duplicates or very large sizes.
Optimized Solution
We can rewrite the code to improve efficiency by using a dictionary (hash map). A dictionary allows us to store values and their indices for quick lookup, reducing the time complexity to O(n).
Here's the optimized version:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
"""
Find two indices in the array such that the numbers at those indices add up to the target.
Args:
nums (List[int]): The list of integers to check.
target (int): The target sum to find.
Returns:
List[int]: A list with 2 indices or an empty list.
"""
num_map = {}
for i, num in enumerate(nums):
# Calculate the value needed to reach the target
other_val = target - num
# Check if the required value is already in the dictionary
if other_val in num_map:
return [num_map[other_val], i]
# Store the current number's index in the dictionary
num_map[num] = i
# Return an empty list if no solution exists
return []
How the Optimized Code Works
Step 1: Create a Dictionary
num_map dict stores every number in the array as a key and its index as the value.
Step 2: Calculate the Complement
For each number in the array, calculate the complement needed to reach the target(other_val).
Step 3: Check the Dictionary
If the complement (other_val) exists in the dictionary, return the current index and the complement's index.
Step 4: Keep the Current Number in the dictionary
If the complement isn't found, add the number(current) and its index to the dictionary - future lookups.
A dict lookup takes O(1).
The loop traverses the array O(n) once.
Comparison of Solutions
Feature Original Code Optimized Code
Time Complexity O(n²) O(n)
Space Complexity O(1) O(n)
Ease of Understanding Moderate High
Performance on Large Inputs Slow Fast
Conclusion: The Power of Hash Maps in Solving Two Sum
The optimized solution demonstrates how using a dictionary (hash map) can significantly improve the efficiency of your code. By avoiding repeated searches with .index() and .count(), we reduced the time complexity from O(n²) to O(n).
If you're solving similar problems, consider leveraging dictionaries for fast lookups. Experiment with this approach and practice similar challenges to solidify your understanding.
Want to learn more about algorithm optimisation or need help with another coding problem? Let's connect and dive deeper!