How to Solve Two Sum Problem: The Ultimate Guide

If you’ve ever prepared for a coding interview, you’ve definitely seen it. The Two Sum problem is the undisputed classic, the gateway to the world of algorithms. It’s simple to understand but teaches powerful concepts.

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

This guide will walk you through three ways to solve the Two Sum problem. We’ll start with the straightforward approach and advance to the most efficient one. Let’s break it down.

1. The Brute Force Approach: Simple but Slow

The most intuitive solution is to check every possible pair of numbers. We use two nested loops. The outer loop picks a number, and the inner loop checks it against every other number to see if they sum to the target.

It’s easy to understand but inefficient. For an array of size n, it checks n*(n-1)/2 pairs. We say it has a time complexity of O(n²).

Here’s the code in Python:

def two_sum_brute_force(nums, target):
    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 []  # No solution found

# Example
nums = [2, 7, 11, 15]
target = 9
print(two_sum_brute_force(nums, target))  # Output: [0, 1]

When to use it? Only for very small arrays. It’s a starting point for understanding the problem.

2. The Hash Map Approach: Fast and Efficient

This is the optimal solution for most cases. It trades space for speed. The idea is to use a hash map (a dictionary in Python) to remember numbers we’ve already seen and their indices.

As we iterate through the array, for each number, we calculate its complement (target – current number). We then check if this complement is already in our hash map. If it is, we’ve found our pair! If not, we store the current number and its index for future checks.

This method only requires a single pass through the array. The time complexity is O(n), and the space complexity is O(n).

def two_sum_hash_map(nums, target):
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []  # No solution found

# Example
nums = [2, 7, 11, 15]
target = 9
print(two_sum_hash_map(nums, target))  # Output: [0, 1]

Step-by-step for the example:

1. i=0, num=2. Complement = 7. Is 7 in seen? No. Store: seen = {2: 0}
2. i=1, num=7. Complement = 2. Is 2 in seen? Yes! Return [seen[2] (which is 0), 1]

This is the solution you should use in interviews. It’s efficient and demonstrates knowledge of hash tables.

3. The Two-Pointer Approach: When You Need the Numbers, Not Indices

This approach is useful if the problem asks for the numbers themselves, not their original indices. A major caveat: it requires the array to be sorted.

We place one pointer at the start (left) and one at the end (right) of the sorted array. We check the sum of the values at these pointers.

• If the sum equals the target, we’re done!
• If the sum is less than the target, we need a larger sum. We move the left pointer right.
• If the sum is greater than the target, we need a smaller sum. We move the right pointer left.

We repeat this until the pointers meet. This has O(n log n) time complexity due to the sorting step.

def two_sum_two_pointers(nums, target):
    # This finds the numbers, not the original indices.
    nums_sorted = sorted(nums)  # Sort the array
    left, right = 0, len(nums_sorted) - 1

    while left < right:
        current_sum = nums_sorted[left] + nums_sorted[right]
        if current_sum == target:
            # We return the values, not the original indices
            return [nums_sorted[left], nums_sorted[right]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []  # No solution found

# Example
nums = [11, 2, 15, 7]  # Original indices don't matter for result
target = 9
print(two_sum_two_pointers(nums, target))  # Output: [2, 7]

When to use it? This is great for finding the values, especially in a sorted array. It’s also the foundation for solving the “Three Sum” problem.

Which Solution Should You Choose?

Your choice depends on the problem’s requirements:

• For interviews, always lead with the Hash Map solution. It’s the most efficient and works for any input.
• Use the Brute Force method only to explain the problem simply.
• Use the Two-Pointer technique if the array is sorted or you need the values, not the indices.

Understanding all three methods gives you a complete toolkit for solving two sum problem. You’ve now mastered the fundamentals of how to solve the Two Sum problem. Practice them, and you’ll be ready to tackle this classic question with confidence.

Here are some related articles that you might want to read:
Data Science Vs Data Analytics: The Battle For The Best Career In Tech
Data Science in Finance: What you need to know
Understanding Data Structures: A Comprehensive Guide