The Problem

Given an array of integers nums and a target integer target, return the indices of the two numbers that add up to the target. You may assume exactly one valid answer exists, and you cannot use the same element twice.

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]  # because nums[0] + nums[1] = 2 + 7 = 9

Why This Problem Matters

Two Sum appears constantly in coding interviews — not because it's hard, but because it tests whether you can recognize when a brute-force solution can be optimized using a different data structure. The jump from O(n²) to O(n) is exactly the kind of thinking interviewers are looking for.

Solution 1: Brute Force — O(n²)

The most straightforward approach: check every pair of numbers.

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 []
  • Time Complexity: O(n²) — nested loops over the array
  • Space Complexity: O(1) — no extra data structures
  • Verdict: Works, but too slow for large inputs. Never submit this in an interview without acknowledging the trade-off.

Solution 2: Sorting + Two Pointers — O(n log n)

Sort the array, then use two pointers (one at each end) moving toward each other. The catch: sorting loses original indices, so you need to store them.

def two_sum_sorted(nums, target):
    indexed = sorted(enumerate(nums), key=lambda x: x[1])
    left, right = 0, len(indexed) - 1
    while left < right:
        s = indexed[left][1] + indexed[right][1]
        if s == target:
            return [indexed[left][0], indexed[right][0]]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []
  • Time Complexity: O(n log n) — dominated by sorting
  • Space Complexity: O(n) — for the indexed pairs
  • Verdict: Better than brute force, but still not optimal.

Solution 3: Hash Map — O(n) ✅ Optimal

This is the solution interviewers expect. As you iterate, store each number's index in a hash map. For each new number, check if its complement (target - num) already exists in the map.

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

Trace Through the Example

inumcomplementseenResult
027{}7 not found, add 2→0
172{2:0}2 found! Return [0, 1]
  • Time Complexity: O(n) — single pass through the array
  • Space Complexity: O(n) — hash map storage
  • Verdict: Optimal. This is your answer.

Key Takeaways

  • Always start by understanding the brute force — then ask yourself what repeated work can be eliminated.
  • Hash maps turn O(n) lookups into O(1), enabling many O(n²) problems to become O(n).
  • The trade-off is space: O(n) extra memory for the hash map.
  • This pattern — store what you've seen, check for a complement — applies to many interview problems beyond Two Sum.

Variations to Practice

  1. Three Sum: Find all triplets that sum to zero.
  2. Two Sum II: Array is already sorted — can you do it in O(1) space?
  3. Subarray Sum Equals K: Find a contiguous subarray summing to k.

Mastering Two Sum in all its forms builds the intuition for a whole family of hash-map-based solutions. It's one of the best problems to thoroughly understand before any coding interview.