Python Algorithms

Two Sum Problem in Python

Find two numbers that add up to a target in a single pass, using a dictionary to remember what you have seen.

  • Intermediate
  • 2 min read
  • 1 runnable example
What you'll learn
  • The complement target - value
  • Storing seen values in a dict
  • O(n) time instead of O(n²)
[2, 7, 11, 15], target 9
index 0: 2need 7, not seen yet → seen = {2: 0}
index 1: 7need 2, found at 0 → [0, 1]

Look for the missing partner

The problem

Given a list of prices and a budget, which two items cost exactly the budget? Checking every pair works but takes about n² / 2 comparisons. Remembering what you have already seen makes it possible in one pass.

Think of it like this

Two Sum is like shopping with an exact budget. For each price tag you work out the amount still missing, then check your notes: have I already seen an item with exactly that price? If yes, the pair is found. If not, you note this price and where you saw it, and move on.

From shopping with a budget to code
complement = target - value🤔 The price still missing
if complement in seen:📋 Is that price already in my notes?
return [seen[complement], index]🛍️ Found the pair: both positions
seen[value] = index✍️ Note this price and its position, then keep going
Look up the missing price instead of checking every pair.
In one sentence

The Two Sum problem asks for the positions of two numbers in a list that add up to a target; a dictionary of seen values solves it in one pass, O(n) time.

Key points

  1. complement = target - value is the value that would complete the pair.
  2. seen maps each value already visited to its index, so lookups are fast.
  3. if complement in seen: finds the partner among earlier values.
  4. seen[value] = index is stored after the check, so a value is never paired with itself.
  5. For 9, the value 7 finds its partner 2 at index 0, giving [0, 1].

When should you use it?

  • Finding pairs with a given sum or difference.
  • Learning to trade memory for speed with a hash table.
  • A very common interview question and the base of 3-Sum and similar problems.

When not to use it

  • Sorted input where memory is tight: two pointers from both ends use no extra memory.
  • You need every pair, not just one: collect results instead of returning at the first match.

Example code

Run code →
main.py
def two_sum(values, target):
    seen = {}
    for index, value in enumerate(values):
        complement = target - value
        if complement in seen:
            return [seen[complement], index]
        seen[value] = index
    return []

print(two_sum([2, 7, 11, 15], 9))
Get a Run button for this example

Result of running the code

[0, 1]

Code explanation

The dictionary stores values already visited. Looking up the required complement makes the algorithm O(n) time with O(n) extra space.

Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.

Practice exercises

Modify the runnable example with the exercises below to build understanding beyond copying the result.

  1. Try empty, single-item, and duplicate-value inputs.
  2. Print state after every step to observe the algorithm.
  3. Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Run in the Python compiler →

Common mistakes

Storing before checking

A value can pair with itself, such as 3 + 3 = 6 with only one 3.

Problem
seen[value] = index
if target - value in seen:
Fix
if target - value in seen:
    return [seen[target - value], index]
seen[value] = index

Finished this lesson?

Mark it as learned to track your progress.

Practice with a challenge

Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.

All challenges