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:** O(n²)

**Space Complexity:** 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:** O(n)

**Space Complexity:** 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:** O(n log n) if sorting is needed, O(n) if already sorted

**Space Complexity:** O(1)

Key Takeaways

1. **Brute Force:** Always works but slow

2. **Hash Map:** Best for unsorted arrays

3. **Two Pointers:** Best for sorted arrays

Understanding these patterns will help you solve similar problems efficiently!