Two Sum Problem in Python

Two Sum Problem in Python

Given a list of numbers and a target value, find the indices of two numbers that add up to the target. This is one of the most popular LeetCode-style interview questions.

Brute Force — O(n²)

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

print(two_sum_brute([2, 7, 11, 15], 9))  # Output: [0, 1]

Optimal Solution Using a Hash Map — O(n)

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

print(two_sum([2, 7, 11, 15], 9))   # Output: [0, 1]
print(two_sum([3, 2, 4], 6))        # Output: [1, 2]

How the Hash Map Works

For each number, calculate its complement (target – number). If that complement was already seen, we have our pair. Otherwise, store the current number and index. This gives O(n) time and O(n) space.

Key Takeaway

Always aim for the hash map solution in interviews. It demonstrates awareness of time complexity trade-offs and is the expected optimal answer.