Two Sum Problem: Multiple Approaches Explained

The Two Sum problem is one of the most frequently asked questions in coding interviews. It's a perfect problem to understand different algorithmic approaches and their trade-offs.

Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example.

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Approach 1. Brute force (O(n²))

The simplest approach is to check every pair of numbers.

def twoSum(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 []

Time complexity is O(n²).

Space complexity is O(1).

While this works, it's inefficient for large arrays.

Approach 2. Hash map (O(n))

We can optimize by using a hash map to store numbers we've seen.

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

Time complexity is O(n).

Space complexity is O(n).

This is the optimal solution for the general case.

Approach 3. Two pointers (O(n log n))

If the array is sorted, we can use two pointers.

def twoSum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

Time complexity is O(n log n) if you must sort first, or O(n) if the input is already sorted.

Space complexity is O(1) for the two-pointer walk itself, plus whatever the sort needs if you sort.

What to remember

Understanding these patterns will help you solve similar problems efficiently!