Course contentsShow
← Computer Science
Lesson 448 of 2,87210. Hash TablesFree lesson

Two-Sum and Complement Problems

Using hash tables to solve complement-finding problems like finding pairs that sum to a target in O(n) time.

Two-Sum and Complement Problems

What you'll learn: How to use hash tables to find pairs of numbers that sum to a target value in linear time.

The Core Idea

The "Two-Sum" problem asks: given an array of numbers and a target sum, find two numbers that add up to that target. The naive approach checks every possible pair, taking O(n²) time. Hash tables let you solve this in just O(n) time by storing complements as you go.

How It Works

The key insight is recognizing that for each number x you examine, you're really looking for its complement: target - x. Instead of searching the entire array each time, you use a hash table to remember numbers you've already seen.

The algorithm:

  1. Create an empty hash table
  2. For each number in the array:
    • Calculate its complement: complement = target - current_number
    • Check if the complement exists in the hash table
    • If yes: you've found your pair!
    • If no: add the current number to the hash table and continue

Why This Works

Think of it like a guest list at a party. You're pairing people for a dance competition where partners' heights must sum to exactly 12 feet. As each guest arrives, you check your list: "Is there someone here who's the perfect height to pair with this person?" If not, you write down the new guest's height and wait. With a hash table, this "check the list" operation is O(1), making the whole process O(n).

This technique extends beyond Two-Sum: anytime you need to find elements with a specific relationship (sum, difference, etc.), consider whether storing complements in a hash table can eliminate nested loops.

Key Takeaway: Hash tables transform complement-finding problems from O(n²) brute-force searches into O(n) single-pass solutions by trading space for time—storing seen values for instant lookup.