Understanding the Two Sum Problem
The Two Sum problem is a classic algorithmic challenge that tests your ability to work with arrays and optimize for performance. The problem statement is simple: given an array of integers and a target sum, find two numbers in the array that add up to the target.
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9
1. Brute Force Approach
The simplest solution is to check every possible pair of numbers in the array.
Checking pairs: (2,7) → Found! 2 + 7 = 9
def twoSum_bruteforce(nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
Time: O(n²)
Space: O(1)
2. Two Pointers Approach
This approach involves sorting the array first, then using two pointers to find the target sum.
Left pointer at 2, Right pointer at 15
def twoSum_twoPointers(nums: List[int], target: int) -> List[int]:
nums_with_index = [(num, i) for i, num in enumerate(nums)]
nums_with_index.sort(key=lambda x: x[0])
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums_with_index[left][0] + nums_with_index[right][0]
if current_sum == target:
return [nums_with_index[left][1], nums_with_index[right][1]]
elif current_sum < target:
left += 1
else:
right -= 1
return []
Time: O(n log n)
Space: O(n)
3. Hash Map Approach (Optimal Solution)
The most efficient approach uses a hash map to store visited numbers and their indices.
Hash Map:
{2: 0} → Found complement 7 at index 1
def twoSum_hashmap(nums: List[int], target: int) -> List[int]:
num_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_map:
return [num_map[complement], i]
num_map[num] = i
return []
Time: O(n)
Space: O(n)
Implementation Tips
- Always clarify if the array is sorted and if you can modify it
- Ask about the expected output format (indices or values)
- Consider edge cases: empty array, no solution, multiple solutions
- Think about space-time trade-offs when choosing an approach
Common Edge Cases to Consider
# Empty array
nums = [], target = 1
# No solution exists
nums = [1, 2, 3], target = 7
# Multiple possible solutions
nums = [3, 3, 3], target = 6
# Negative numbers
nums = [-1, -2, -3], target = -5
# Single element
nums = [1], target = 1
Launch your Graphy