Two Sum Algorithm in Python

Welcome to LeetCode #1, the most famous coding puzzle on Earth! 🌍 The leetcode two sum problem is the gateway drug to algorithmic thinking and the moment the hash map python lightbulb finally clicks. 💡

It looks simple — find two numbers that add up to a target — but tucked inside this array problem is a gorgeous lesson about trading memory for speed. By the end you will know three solutions and why this interview question has stayed #1 for over a decade.

The Problem Statement

Given an array nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution, and you may not use the same element twice.

Quick examples:

We return indices, not values. That detail trips up more people than you would believe.

Approach 1: Brute Force

The most natural first instinct: just try every pair. 🐢

for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        if nums[i] + nums[j] == target:
            return [i, j]

O(n^2) time, O(1) space. For length 10,000 that is ~50M checks. Still acceptable for tiny n, throwaway scripts, or as a baseline before optimising. Interviewers want to hear "naive is O(n^2), can we do better?" ✅

Approach 2: Two-Pass Hash Map

First leap into hash-map land: build a dictionary of value → index, then loop again looking for the complement.

def two_sum_two_pass(nums, target):
    num_map = {num: i for i, num in enumerate(nums)}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map and num_map[complement] != i:
            return [i, num_map[complement]]
    return []

O(n) time, O(n) space. The != i check is critical — without it, [3, 5] with target = 6 would return [0, 0]. We cannot reuse the same element. ⚠️

Approach 3: One-Pass Hash Map

The elegant trick: *check the map while you are building it*. The first time you see a number, record it. When its partner shows up later, the earlier number is already waiting.

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

Worked example: `nums = [2, 7, 11, 15]`, `target = 9`

Two iterations, done. ⚡ We never even look at 11 or 15. The single-pass version is also safer — we always look backwards into a map that does not yet contain the current element.

Complexity Analysis

A textbook space–time tradeoff: O(n) memory slashes time from quadratic to linear — a model that carries through DP, memoisation, and graph algorithms.

Common Pitfalls

1. Returning values instead of indices. The problem asks for [i, j], not [nums[i], nums[j]]. 👀

2. Returning the same index twice. If target = 2 * nums[i] and you do not guard against j == i, you may pair an element with itself. The one-pass version sidesteps this naturally.

3. Mishandling duplicates. nums = [3, 3], target = 6 is legit — your logic must allow two equal values at different indices.

4. Mutating the input. Sorting nums to use two pointers destroys original indices. If you must sort, sort (value, index) tuples instead.

5. Assuming a solution always exists. LeetCode #1 guarantees one; real life does not. Decide your no-pair return value ([], None, raise) and document it.

6. Confusing this with the sorted variant. Sorted input (LC 167) calls for two pointers in O(1) space, not a hash map. Different problem, different tool.

Variants You Will See

Why Interviewers Love This Problem

Two Sum is a near-perfect 15-minute screen. One small problem grades:

A vibes check disguised as an algorithm. 🕵️

Real-World Uses

The "two values summing to a target" pattern is everywhere once you spot it:

Frequently Asked Questions

Why is the hash map approach $O(n)$? Each iteration is an O(1) average-case dict lookup plus insert. Done n times, that is O(n) total. Python's dict is engineered to avoid the pathological collision case.

Multiple valid pairs? LeetCode #1 promises one. In real inputs, decide: first found, all pairs, or lex-smallest.

What if no pair sums to target? Return a sentinel — [], None, or raise ValueError. Our code returns []. Pick a convention and stick to it.

Should I sort and use two pointers? Only if it is already sorted or you do not need original indices. Sorting is O(n log n), worse than the hash map's O(n).

Does it work with negative numbers? Yes. complement = target - num is happy with negatives, zero, and floats. nums = [-3, 4, 3, 90], target = 0 returns [0, 2].

Two Sum vs 3Sum — how does it generalise? k-Sum is "fix one element, run (k-1)-Sum on the rest", with Two Sum as the base case. Master Two Sum and half of 3Sum is done. 🎯