Solving Two Sum Problem in Python: Step-by-Step Guide

Introduction to the Two Sum Problem

The Two Sum problem is one of the most iconic algorithmic challenges in computer science. It is frequently the first problem developers encounter on platforms like LeetCode, and it serves as a foundational exercise for understanding hash maps, array traversal, and time-space tradeoffs. Despite its apparent simplicity, the problem reveals a great deal about how a developer thinks about optimization.

In its classic form, the problem asks: given an array of integers and a target integer, return the indices of the two numbers that add up to the target. You may assume that each input has exactly one solution, and you cannot use the same element twice.

Why It Matters

Two Sum is more than a coding interview warm-up. It teaches essential concepts that appear across real-world engineering tasks: lookup tables, complementary value matching, and the difference between O(n²) and O(n) algorithms. Whether you are building a reconciliation system that matches invoices to payments, a feature that pairs users with complementary skills, or a financial tool that finds transactions summing to a specific amount, the underlying pattern is the same.

Understanding the Problem Statement

Before writing any code, it is critical to fully understand the requirements. Let us restate the problem formally:

You are given an array nums of integers.
You are given an integer target.
You must return the indices of two distinct elements whose values sum to target.
Exactly one valid solution is guaranteed to exist.
The order of the returned indices does not matter.

For example, given nums = [2, 7, 11, 15] and target = 9, the answer is [0, 1] because nums[0] + nums[1] = 2 + 7 = 9.

Approach 1: The Brute Force Solution

The most intuitive approach is to compare every possible pair of numbers in the array. For each element, iterate through every subsequent element and check whether their sum equals the target. This is a nested loop solution.

Implementation

def two_sum_brute(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 usage
nums = [2, 7, 11, 15]
target = 9
print(two_sum_brute(nums, target))  # Output: [0, 1]

Analysis

This solution is correct but inefficient. The outer loop runs n times, and the inner loop runs up to n - 1 times, giving a time complexity of O(n²). The space complexity is O(1) because no additional data structures are used.

For small arrays, this is acceptable. However, if the array contains hundreds of thousands of elements, the quadratic runtime becomes a serious bottleneck. This motivates the search for a more efficient approach.

Approach 2: The Hash Map Solution

The key insight is that for each number x, we are looking for another number target - x. Instead of scanning the array repeatedly to find this complement, we can store numbers we have already seen in a hash map. A hash map provides average O(1) lookup time, which dramatically improves performance.

The algorithm works as follows: iterate through the array once. For each element, compute its complement. If the complement already exists in the hash map, return the current index and the stored index. Otherwise, store the current element along with its index in the hash map.

Implementation

def two_sum_hash(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 usage
nums = [2, 7, 11, 15]
target = 9
print(two_sum_hash(nums, target))  # Output: [0, 1]

Analysis

This solution runs in O(n) time because we traverse the array only once, and each hash map operation is O(1) on average. The space complexity is O(n) in the worst case, since we may need to store nearly every element in the hash map before finding the solution.

This tradeoff — exchanging extra memory for faster runtime — is one of the most common patterns in algorithm design. The hash map approach is the canonical solution to Two Sum and is what most interviewers expect.

Approach 3: Sorting with Two Pointers

There is a third approach worth knowing. If we sort the array first, we can use two pointers — one at the beginning and one at the end — and move them inward based on whether the current sum is too small or too large. This approach is elegant but has a complication: sorting destroys the original indices, so we must track them separately.

Implementation

def two_sum_sorted(nums, target):
    # Pair each value with its original index, then sort by value
    indexed = list(enumerate(nums))
    indexed.sort(key=lambda pair: pair[1])

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

# Example usage
nums = [3, 2, 4]
target = 6
print(two_sum_sorted(nums, target))  # Output: [1, 2]

Analysis

The sorting step dominates the runtime, giving a time complexity of O(n log n). The two-pointer traversal itself is O(n). Space complexity is O(n) due to the auxiliary indexed list. This approach is slower than the hash map solution for the classic Two Sum problem, but the two-pointer technique is invaluable for related problems such as Three Sum, where hash maps become more cumbersome.

Handling Edge Cases

A robust solution must account for edge cases that may not appear in the basic problem statement. Consider the following scenarios:

Negative numbers: The array may contain negative values. The hash map approach handles these naturally because the complement calculation works regardless of sign.
Duplicate values: If the array contains duplicates, such as [3, 3] with target 6, the hash map approach still works because we check for the complement before inserting the current element.
Large inputs: For very large arrays, the O(n) hash map solution is essential. The brute force approach would be prohibitively slow.
No solution exists: Although the classic problem guarantees a solution, real-world code should handle the case gracefully by returning an empty list or raising a custom exception.

Here is an example that demonstrates handling duplicates correctly:

def two_sum_safe(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    raise ValueError("No two sum solution exists")

# Duplicate values
print(two_sum_safe([3, 3], 6))        # Output: [0, 1]
# Negative numbers
print(two_sum_safe([-1, -2, -3, -4], -6))  # Output: [1, 3]

Best Practices

When implementing Two Sum or similar lookup-based algorithms, keep the following best practices in mind:

Prefer the hash map approach for the classic Two Sum problem. It offers the best time complexity and is straightforward to implement.
Check the complement before inserting the current element into the hash map. This prevents accidentally using the same element twice when duplicates are present.
Use meaningful variable names such as complement and seen rather than cryptic single letters. This improves readability and maintainability.
Document assumptions in your code. If you assume exactly one solution exists, state it in a docstring so future maintainers understand the contract.
Write tests covering normal cases, edge cases, and error cases. A small test suite prevents regressions when the function is modified later.

Here is a fully documented version with a docstring and type hints:

from typing import List

def two_sum(nums: List[int], target: int) -> List[int]:
    """
    Find two distinct indices whose values sum to the target.

    Args:
        nums: List of integers.
        target: Target sum.

    Returns:
        A list containing the two indices.

    Raises:
        ValueError: If no valid pair exists.
    """
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    raise ValueError("No two sum solution exists")

Performance Comparison

To appreciate the difference between approaches, consider how each scales with input size. The table below summarizes the complexities:

Brute force: O(n²) time, O(1) space
Hash map: O(n) time, O(n) space
Sorting with two pointers: O(n log n) time, O(n) space

For an array of 100,000 elements, the brute force approach may perform roughly 5 billion comparisons, while the hash map approach performs around 100,000 hash map operations. This is the difference between a program that finishes in milliseconds and one that takes minutes.

Conclusion

The Two Sum problem is a deceptively simple challenge that opens the door to fundamental algorithmic thinking. By progressing from the brute force O(n²) solution to the elegant O(n) hash map approach, developers learn how to identify complementary relationships and leverage data structures for dramatic performance gains. The two-pointer sorting variant further enriches the toolkit, proving useful for related problems. Mastering Two Sum is not just about passing an interview — it is about internalizing a pattern of lookup-based optimization that recurs throughout software engineering. With a solid understanding of these approaches, their tradeoffs, and the edge cases they handle, you are well equipped to tackle not only Two Sum but the broad family of problems it represents.