Two-Sum and Pair Problems — Common Hashing Patterns &… | OneNoughtOne

0/361

Data Structures & AlgorithmsHash Tables

Common Hashing Patterns & Problem Types

LevelIntermediate

Duration75 mins

TopicHash Tables

2 / 5

Two-Sum and Pair Problems

The Gateway Problem

If there's one problem that has launched a million coding careers, it's Two-Sum . This deceptively simple problem appears as the first challenge on most coding platforms for good reason: it perfectly illustrates the power of hash tables to transform brute-force O(n²) solutions into elegant O(n) algorithms. The problem statement is disarmingly simple: Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target . A beginner might think, "That's easy—just check every pair." And they'd be right, but their solution would be slow. The hash table approach reveals a profound insight: instead of searching for a pair, search for the complement . This mental shift—from "find two things that work together" to "for each thing, check if its partner exists"—is one of the most powerful pattern transformations in algorithm design. It applies far beyond Two-Sum to problems involving pairs, triples, and arbitrary k-tuples.

What You Will Master

By the end of this page, you will understand the Two-Sum pattern at a fundamental level—not just as an interview problem, but as a template for recognizing and solving an entire class of complement-based lookup problems. You'll see variants involving triplets, differences, products, and streaming data.

The Brute Force Baseline

Before appreciating the hash table solution, we must understand what we're optimizing away. The brute force approach is intuitive: Algorithm: For each element at index i For each element at index j where j > i If nums[i] + nums[j] == target, return [i, j] This is the "check all pairs" approach—correct, but inefficient.

two_sum_brute_force
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Two Sum: Brute Force Approach
 * Time: O(n²) - nested loops check all pairs
 * Space: O(1) - no extra data structures
 */
function twoSumBruteForce(nums: number[], target: number): [number, number] | null {
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    
    return null; // No solution found
}
 
// Analysis of the nested loop:
// When i = 0: j runs from 1 to n-1 → n-1 comparisons
// When i = 1: j runs from 2 to n-1 → n-2 comparisons
// ...
// When i = n-2: j runs from n-1 to n-1 → 1 comparison
// Total: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)
 
// Example
console.log(twoSumBruteForce([2, 7, 11, 15], 9)); // [0, 1]

Why is O(n²) problematic? The quadratic growth means the solution doesn't scale:

Input Size	Comparisons (Brute Force)	Time at 10⁶ ops/sec
1,000	499,500	0.5 seconds
10,000	49,995,000	50 seconds
100,000	4,999,950,000	83 minutes
1,000,000	499,999,500,000	5.8 days

For any non-trivial input size, we need a better approach.

The Hash Table Insight

The key insight that transforms Two-Sum from O(n²) to O(n) is a change in perspective: Brute Force Thinking: "For each pair (i, j), check if nums[i] + nums[j] = target" Hash Table Thinking: "For each element nums[i], check if (target - nums[i]) exists somewhere in the array" The difference is subtle but profound: Brute force: We're looking for pairs Hash table: We're looking for complements The Complement: If we need two numbers that sum to target, and one of them is x, then the other must be target - x . This number is called the complement of x with respect to target. complement(x) = target - x Now the problem becomes: "For each x in the array, does complement(x) also exist in the array?" This is a membership query —exactly what hash tables solve in O(1) time!

The Core Pattern

The Two-Sum insight generalizes: whenever you're searching for elements that combine in some way (sum, difference, product, XOR), ask yourself: 'Can I compute what the other element MUST be, and then check if it exists?' If yes, replace nested iteration with a hash lookup.

two_sum_hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * Two Sum: Hash Table Approach (Two-Pass)
 * Time: O(n) - two sequential passes
 * Space: O(n) - hash table stores up to n elements
 * 
 * Pass 1: Build a map from value → index
 * Pass 2: For each element, look up its complement
 */
function twoSumTwoPass(nums: number[], target: number): [number, number] | null {
    // Pass 1: Build the lookup table
    const valueToIndex = new Map<number, number>();
    for (let i = 0; i < nums.length; i++) {
        valueToIndex.set(nums[i], i);
    }
    
    // Pass 2: Find complements
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        const complementIndex = valueToIndex.get(complement);
        
        // Check: complement exists AND is not the same element
        if (complementIndex !== undefined && complementIndex !== i) {
            return [i, complementIndex];
        }
    }
    
    return null;
}
 
/**
 * Two Sum: Hash Table Approach (One-Pass)
 * Time: O(n) - single pass
 * Space: O(n) - hash table stores up to n elements
 * 
 * Key insight: As we iterate, we check if complement was seen BEFORE
 * This handles the "don't use same element twice" constraint naturally
 */
function twoSumOnePass(nums: number[], target: number): [number, number] | null {
    const valueToIndex = new Map<number, number>();
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        
        // Check if complement was seen in previous elements
        if (valueToIndex.has(complement)) {
            return [valueToIndex.get(complement)!, i];
        }
        
        // Add current element to the map (after checking!)
        valueToIndex.set(nums[i], i);
    }
    
    return null;
}
 
// Example walkthrough of one-pass:
// nums = [2, 7, 11, 15], target = 9
// i=0: complement = 9-2 = 7, map = {} → 7 not found → add 2:0 → map = {2:0}
// i=1: complement = 9-7 = 2, map = {2:0} → 2 found at index 0! return [0, 1]
 
console.log(twoSumOnePass([2, 7, 11, 15], 9)); // [0, 1]

Handling Edge Cases

Two-Sum has several edge cases that trip up even experienced developers. Understanding these edge cases reveals deeper insights about the algorithm. Edge Case 1: Duplicate Values What if the array contains duplicates? Consider: nums = [3, 3], target = 6 The brute force finds indices [0, 1]. Does the hash approach?

two_sum_duplicates
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Edge Case: Duplicates
// nums = [3, 3], target = 6
 
// Two-pass approach with duplicates:
// Pass 1: Build map → {3: 1} (second occurrence overwrites first!)
// Pass 2: i=0, complement=3, map[3]=1, 1 !== 0 → return [0, 1] ✓
 
// One-pass approach with duplicates:
// i=0: complement = 3, map = {} → not found → add 3:0 → map = {3:0}
// i=1: complement = 3, map = {3:0} → found at index 0! → return [0, 1] ✓
 
// Both work! But for different reasons:
// - Two-pass: We check complementIndex !== i, so overwriting is safe
// - One-pass: We find the PREVIOUS occurrence naturally
 
function twoSumDuplicatesSafe(nums: number[], target: number): [number, number] | null {
    const valueToIndex = new Map<number, number>();
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        
        // For duplicates summing to target, the complement IS the current value
        // But we check the map BEFORE adding, so we find the earlier index
        if (valueToIndex.has(complement)) {
            return [valueToIndex.get(complement)!, i];
        }
        
        valueToIndex.set(nums[i], i);
    }
    
    return null;
}
 
console.log(twoSumDuplicatesSafe([3, 3], 6)); // [0, 1] ✓

Edge Case 2: Self-Complement (target = 2x) What if an element is its own complement? For example: nums = [3, 2, 4], target = 6 Element 3 is its own complement (3 + 3 = 6) But there's only one 3, so we can't use it twice! The one-pass approach handles this naturally because we check the map before adding the current element.

self_complement
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Edge Case: Self-complement with only one occurrence
// nums = [3, 2, 4], target = 6
 
// One-pass trace:
// i=0: num=3, complement=6-3=3, map={} → 3 not found → add 3:0
// i=1: num=2, complement=6-2=4, map={3:0} → 4 not found → add 2:1  
// i=2: num=4, complement=6-4=2, map={3:0, 2:1} → 2 found! → return [1, 2]
 
// The 3 correctly doesn't match with itself because complement (3)
// isn't in the map when we're processing the 3.
 
// Counter-example where self-complement SHOULD match:
// nums = [3, 3, 2, 4], target = 6
// i=0: num=3, complement=3, map={} → not found → add 3:0
// i=1: num=3, complement=3, map={3:0} → found! → return [0, 1] ✓

Edge Case 3: Negative Numbers Negative numbers work identically—the complement calculation handles them naturally: If nums[i] = -5 and target = 3, then complement = 3 - (-5) = 8 Edge Case 4: Zero Zero is a valid element and value: nums = [0, 4, 3, 0], target = 0 \to complement of 0 = 0 \to indices [0, 3] Edge Case 5: No Solution Always consider the possibility that no valid pair exists. The hash approach naturally returns after exhausting all elements.

Interview Tip

Always clarify assumptions with your interviewer: • Can there be multiple solutions? (Usually, assume exactly one) • Can the same element be used twice? (Usually, no) • Are there negative numbers? (Usually, yes—handle them) • What if no solution exists? (Return empty/null/throw?)

Two-Sum Variants

The Two-Sum pattern extends to numerous variants, each requiring slight modifications to the core algorithm. Variant 1: Two Sum with Sorted Input If the input is sorted, we can use the two-pointer technique instead of hashing—achieving O(1) space:

two_sum_sorted
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Two Sum II: Input is Sorted (Two Pointer Approach)
 * Time: O(n), Space: O(1)
 * 
 * Key insight: If sum is too small, move left pointer right
 *              If sum is too large, move right pointer left
 */
function twoSumSorted(nums: number[], target: number): [number, number] | null {
    let left = 0;
    let right = nums.length - 1;
    
    while (left < right) {
        const sum = nums[left] + nums[right];
        
        if (sum === target) {
            return [left, right];
        } else if (sum < target) {
            left++;  // Need larger sum, move left pointer right
        } else {
            right--; // Need smaller sum, move right pointer left
        }
    }
    
    return null;
}
 
// Example: nums = [2, 7, 11, 15], target = 9
// left=0 (2), right=3 (15): sum=17 > 9 → right--
// left=0 (2), right=2 (11): sum=13 > 9 → right--
// left=0 (2), right=1 (7): sum=9 = 9 → return [0, 1]
 
console.log(twoSumSorted([2, 7, 11, 15], 9)); // [0, 1]

Variant 2: Two Sum - Find All Pairs Instead of finding one pair, find all pairs that sum to target:

two_sum_all_pairs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Two Sum: Find All Pairs (by indices)
 * Time: O(n), Space: O(n)
 * 
 * Key insight: Store ALL indices for each value, not just one
 */
function twoSumAllPairs(nums: number[], target: number): [number, number][] {
    const result: [number, number][] = [];
    const valueToIndices = new Map<number, number[]>();
    
    // Build map: value → all indices where it appears
    for (let i = 0; i < nums.length; i++) {
        if (!valueToIndices.has(nums[i])) {
            valueToIndices.set(nums[i], []);
        }
        valueToIndices.get(nums[i])!.push(i);
    }
    
    // Find all pairs
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        const complementIndices = valueToIndices.get(complement) ?? [];
        
        for (const j of complementIndices) {
            // Only include pairs where i < j to avoid duplicates
            if (i < j) {
                result.push([i, j]);
            }
        }
    }
    
    return result;
}
 
// Example: nums = [1, 5, 3, 3, 3], target = 6
// Pairs: (1,5), (3,3), (3,3), (3,3) - but which indices?
console.log(twoSumAllPairs([1, 5, 3, 3, 3], 6));
// [[0,1], [2,3], [2,4], [3,4]]

Variant 3: Two Sum - Count Pairs (Unique Values) Count the number of unique pairs that sum to target:

two_sum_count
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Two Sum: Count Unique Value Pairs
 * Time: O(n), Space: O(n)
 * 
 * Count pairs of VALUES (not indices) that sum to target
 */
function countTwoSumPairs(nums: number[], target: number): number {
    const freq = new Map<number, number>();
    
    // Count frequency of each value
    for (const num of nums) {
        freq.set(num, (freq.get(num) ?? 0) + 1);
    }
    
    let count = 0;
    const counted = new Set<number>();
    
    for (const [num, numFreq] of freq) {
        const complement = target - num;
        
        // Skip if we've already counted this pair
        if (counted.has(num)) continue;
        
        if (num === complement) {
            // Self-pairing: need at least 2 of the same value
            // Number of pairs = C(n,2) = n*(n-1)/2
            if (numFreq >= 2) {
                count += (numFreq * (numFreq - 1)) / 2;
            }
        } else if (freq.has(complement)) {
            // Cross-pairing: every occurrence of num can pair with
            // every occurrence of complement
            count += numFreq * freq.get(complement)!;
            counted.add(complement); // Mark complement as counted
        }
        
        counted.add(num);
    }
    
    return count;
}
 
// Example: nums = [1, 5, 3, 3, 3], target = 6
// Pairs: 1+5=6 (1 pair), 3+3=6 (3 choose 2 = 3 pairs) = 4 total
console.log(countTwoSumPairs([1, 5, 3, 3, 3], 6)); // 4

Variant 4: Two Sum - Data Stream Design a data structure that supports adding numbers and checking for pairs:

two_sum_stream
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * TwoSum III - Data Structure Design
 * 
 * Supports:
 * - add(number): Add to the data structure
 * - find(target): Check if any pair sums to target
 */
class TwoSumStream {
    private freq = new Map<number, number>();
    
    /**
     * Add a number to the data structure
     * Time: O(1)
     */
    add(number: number): void {
        this.freq.set(number, (this.freq.get(number) ?? 0) + 1);
    }
    
    /**
     * Check if there exists any pair that sums to target
     * Time: O(n) where n is the number of unique values
     */
    find(target: number): boolean {
        for (const [num, count] of this.freq) {
            const complement = target - num;
            
            if (num === complement) {
                // Need at least 2 occurrences
                if (count >= 2) return true;
            } else {
                // Need complement to exist
                if (this.freq.has(complement)) return true;
            }
        }
        
        return false;
    }
}
 
// Usage
const ts = new TwoSumStream();
ts.add(1);
ts.add(3);
ts.add(5);
console.log(ts.find(4));  // true (1 + 3)
console.log(ts.find(7));  // false (no pair sums to 7... wait, 3+5=8, 1+5=6)
                          // Actually false - no pair sums to exactly 7
ts.add(4);
console.log(ts.find(7));  // true (3 + 4)

Beyond Two-Sum: Three-Sum and K-Sum

Two-Sum naturally extends to finding triplets (Three-Sum) and k-tuples (K-Sum). These problems combine the hash table insight with additional techniques. Three-Sum: Find Triplets Summing to Zero Given an array, find all unique triplets that sum to zero. This is a classic interview problem that combines Two-Sum with an outer loop:

three_sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Three Sum: Find All Unique Triplets
 * 
 * Approach: Sort + Two Pointers (more efficient than hash-based for this problem)
 * Time: O(n²), Space: O(1) excluding output
 * 
 * Key insight: Fix one element, then find Two-Sum on the remaining sorted array
 */
function threeSum(nums: number[]): number[][] {
    const result: number[][] = [];
    const n = nums.length;
    
    // Sorting enables two-pointer technique and easy duplicate skipping
    nums.sort((a, b) => a - b);
    
    for (let i = 0; i < n - 2; i++) {
        // Skip duplicates for the first element
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        
        // If smallest element is positive, no triplet can sum to 0
        if (nums[i] > 0) break;
        
        // Two-pointer Two-Sum for target = -nums[i]
        let left = i + 1;
        let right = n - 1;
        const target = -nums[i];
        
        while (left < right) {
            const sum = nums[left] + nums[right];
            
            if (sum === target) {
                result.push([nums[i], nums[left], nums[right]]);
                
                // Skip duplicates for second and third elements
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return result;
}
 
// Example
console.log(threeSum([-1, 0, 1, 2, -1, -4]));
// [[-1, -1, 2], [-1, 0, 1]]

Four-Sum and General K-Sum The pattern generalizes: for K-Sum, we reduce to (K-1)-Sum, which reduces to (K-2)-Sum, and so on until we reach Two-Sum:

k_sum
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * K-Sum: Generalized Solution
 * Time: O(n^(k-1)) for k-sum
 * 
 * Recursively reduce k-sum to (k-1)-sum until we reach 2-sum (two pointers)
 */
function kSum(nums: number[], target: number, k: number): number[][] {
    nums.sort((a, b) => a - b);
    return kSumHelper(nums, target, k, 0);
}
 
function kSumHelper(
    nums: number[], 
    target: number, 
    k: number, 
    start: number
): number[][] {
    const result: number[][] = [];
    const n = nums.length;
    
    // Base case: 2-sum with two pointers
    if (k === 2) {
        let left = start;
        let right = n - 1;
        
        while (left < right) {
            const sum = nums[left] + nums[right];
            
            if (sum === target) {
                result.push([nums[left], nums[right]]);
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        
        return result;
    }
    
    // Recursive case: reduce k-sum to (k-1)-sum
    for (let i = start; i <= n - k; i++) {
        // Skip duplicates
        if (i > start && nums[i] === nums[i - 1]) continue;
        
        // Pruning: if smallest k elements exceed target, break
        let minSum = 0;
        for (let j = 0; j < k; j++) minSum += nums[i + j];
        if (minSum > target) break;
        
        // Pruning: if nums[i] + largest (k-1) elements < target, skip
        let maxSum = nums[i];
        for (let j = 0; j < k - 1; j++) maxSum += nums[n - 1 - j];
        if (maxSum < target) continue;
        
        // Recurse: find (k-1)-sum for target - nums[i]
        const subResults = kSumHelper(nums, target - nums[i], k - 1, i + 1);
        
        for (const sub of subResults) {
            result.push([nums[i], ...sub]);
        }
    }
    
    return result;
}
 
// Example: 4-sum
console.log(kSum([1, 0, -1, 0, -2, 2], 0, 4));
// [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Summary: The Complement Lookup Pattern

Two-Sum is more than an interview problem—it's a template for recognizing a fundamental pattern in algorithm design. Let's consolidate the key insights:

Key Takeaways

•Transform 'find pair' into 'find complement' — This reframing converts O(n²) to O(n)
•One-pass is preferred — Build the map as you go; check before adding handles edge cases naturally
•The pattern applies to any binary relationship — Sum, difference, product, XOR—any operation where one value determines the other
•K-Sum reduces to Two-Sum — For k > 2, fix elements and reduce until you reach the base case
•Sorted inputs enable O(1) space — Two pointers work when order is guaranteed
•Edge cases matter — Duplicates, self-complements, and zeros require careful handling

Two-Sum Pattern Quick Reference
Relationship	Complement Formula	Example Problem
a + b = target	target - a	Two Sum, Three Sum
a - b = target	a - target or a + target	Pair with difference
a * b = target	target / a (if divisible)	Factor pairs
a XOR b = target	a XOR target	XOR queries
a mod b = target	Depends on context	Modular arithmetic

Page Complete

You now understand the Two-Sum pattern at a deep level—not as a single problem, but as a template for an entire class of complement-based algorithms. This mental model will help you recognize and solve pair-finding problems instantly. Next, we'll explore duplicate detection patterns.

Data Structures & AlgorithmsHash Tables

Common Hashing Patterns & Problem Types

LevelIntermediate

Duration75 mins

TopicHash Tables

2 / 5

Two-Sum and Pair Problems

The Gateway Problem

If there's one problem that has launched a million coding careers, it's Two-Sum . This deceptively simple problem appears as the first challenge on most coding platforms for good reason: it perfectly illustrates the power of hash tables to transform brute-force O(n²) solutions into elegant O(n) algorithms. The problem statement is disarmingly simple: Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target . A beginner might think, "That's easy—just check every pair." And they'd be right, but their solution would be slow. The hash table approach reveals a profound insight: instead of searching for a pair, search for the complement . This mental shift—from "find two things that work together" to "for each thing, check if its partner exists"—is one of the most powerful pattern transformations in algorithm design. It applies far beyond Two-Sum to problems involving pairs, triples, and arbitrary k-tuples.

What You Will Master

By the end of this page, you will understand the Two-Sum pattern at a fundamental level—not just as an interview problem, but as a template for recognizing and solving an entire class of complement-based lookup problems. You'll see variants involving triplets, differences, products, and streaming data.

The Brute Force Baseline

Before appreciating the hash table solution, we must understand what we're optimizing away. The brute force approach is intuitive: Algorithm: For each element at index i For each element at index j where j > i If nums[i] + nums[j] == target, return [i, j] This is the "check all pairs" approach—correct, but inefficient.

two_sum_brute_force
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Two Sum: Brute Force Approach
 * Time: O(n²) - nested loops check all pairs
 * Space: O(1) - no extra data structures
 */
function twoSumBruteForce(nums: number[], target: number): [number, number] | null {
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    
    return null; // No solution found
}
 
// Analysis of the nested loop:
// When i = 0: j runs from 1 to n-1 → n-1 comparisons
// When i = 1: j runs from 2 to n-1 → n-2 comparisons
// ...
// When i = n-2: j runs from n-1 to n-1 → 1 comparison
// Total: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)
 
// Example
console.log(twoSumBruteForce([2, 7, 11, 15], 9)); // [0, 1]

Why is O(n²) problematic? The quadratic growth means the solution doesn't scale:

Input Size	Comparisons (Brute Force)	Time at 10⁶ ops/sec
1,000	499,500	0.5 seconds
10,000	49,995,000	50 seconds
100,000	4,999,950,000	83 minutes
1,000,000	499,999,500,000	5.8 days

For any non-trivial input size, we need a better approach.

The Hash Table Insight

The key insight that transforms Two-Sum from O(n²) to O(n) is a change in perspective: Brute Force Thinking: "For each pair (i, j), check if nums[i] + nums[j] = target" Hash Table Thinking: "For each element nums[i], check if (target - nums[i]) exists somewhere in the array" The difference is subtle but profound: Brute force: We're looking for pairs Hash table: We're looking for complements The Complement: If we need two numbers that sum to target, and one of them is x, then the other must be target - x . This number is called the complement of x with respect to target. complement(x) = target - x Now the problem becomes: "For each x in the array, does complement(x) also exist in the array?" This is a membership query —exactly what hash tables solve in O(1) time!

The Core Pattern

The Two-Sum insight generalizes: whenever you're searching for elements that combine in some way (sum, difference, product, XOR), ask yourself: 'Can I compute what the other element MUST be, and then check if it exists?' If yes, replace nested iteration with a hash lookup.

two_sum_hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * Two Sum: Hash Table Approach (Two-Pass)
 * Time: O(n) - two sequential passes
 * Space: O(n) - hash table stores up to n elements
 * 
 * Pass 1: Build a map from value → index
 * Pass 2: For each element, look up its complement
 */
function twoSumTwoPass(nums: number[], target: number): [number, number] | null {
    // Pass 1: Build the lookup table
    const valueToIndex = new Map<number, number>();
    for (let i = 0; i < nums.length; i++) {
        valueToIndex.set(nums[i], i);
    }
    
    // Pass 2: Find complements
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        const complementIndex = valueToIndex.get(complement);
        
        // Check: complement exists AND is not the same element
        if (complementIndex !== undefined && complementIndex !== i) {
            return [i, complementIndex];
        }
    }
    
    return null;
}
 
/**
 * Two Sum: Hash Table Approach (One-Pass)
 * Time: O(n) - single pass
 * Space: O(n) - hash table stores up to n elements
 * 
 * Key insight: As we iterate, we check if complement was seen BEFORE
 * This handles the "don't use same element twice" constraint naturally
 */
function twoSumOnePass(nums: number[], target: number): [number, number] | null {
    const valueToIndex = new Map<number, number>();
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        
        // Check if complement was seen in previous elements
        if (valueToIndex.has(complement)) {
            return [valueToIndex.get(complement)!, i];
        }
        
        // Add current element to the map (after checking!)
        valueToIndex.set(nums[i], i);
    }
    
    return null;
}
 
// Example walkthrough of one-pass:
// nums = [2, 7, 11, 15], target = 9
// i=0: complement = 9-2 = 7, map = {} → 7 not found → add 2:0 → map = {2:0}
// i=1: complement = 9-7 = 2, map = {2:0} → 2 found at index 0! return [0, 1]
 
console.log(twoSumOnePass([2, 7, 11, 15], 9)); // [0, 1]

Handling Edge Cases

Two-Sum has several edge cases that trip up even experienced developers. Understanding these edge cases reveals deeper insights about the algorithm. Edge Case 1: Duplicate Values What if the array contains duplicates? Consider: nums = [3, 3], target = 6 The brute force finds indices [0, 1]. Does the hash approach?

two_sum_duplicates
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Edge Case: Duplicates
// nums = [3, 3], target = 6
 
// Two-pass approach with duplicates:
// Pass 1: Build map → {3: 1} (second occurrence overwrites first!)
// Pass 2: i=0, complement=3, map[3]=1, 1 !== 0 → return [0, 1] ✓
 
// One-pass approach with duplicates:
// i=0: complement = 3, map = {} → not found → add 3:0 → map = {3:0}
// i=1: complement = 3, map = {3:0} → found at index 0! → return [0, 1] ✓
 
// Both work! But for different reasons:
// - Two-pass: We check complementIndex !== i, so overwriting is safe
// - One-pass: We find the PREVIOUS occurrence naturally
 
function twoSumDuplicatesSafe(nums: number[], target: number): [number, number] | null {
    const valueToIndex = new Map<number, number>();
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        
        // For duplicates summing to target, the complement IS the current value
        // But we check the map BEFORE adding, so we find the earlier index
        if (valueToIndex.has(complement)) {
            return [valueToIndex.get(complement)!, i];
        }
        
        valueToIndex.set(nums[i], i);
    }
    
    return null;
}
 
console.log(twoSumDuplicatesSafe([3, 3], 6)); // [0, 1] ✓

Edge Case 2: Self-Complement (target = 2x) What if an element is its own complement? For example: nums = [3, 2, 4], target = 6 Element 3 is its own complement (3 + 3 = 6) But there's only one 3, so we can't use it twice! The one-pass approach handles this naturally because we check the map before adding the current element.

self_complement
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Edge Case: Self-complement with only one occurrence
// nums = [3, 2, 4], target = 6
 
// One-pass trace:
// i=0: num=3, complement=6-3=3, map={} → 3 not found → add 3:0
// i=1: num=2, complement=6-2=4, map={3:0} → 4 not found → add 2:1  
// i=2: num=4, complement=6-4=2, map={3:0, 2:1} → 2 found! → return [1, 2]
 
// The 3 correctly doesn't match with itself because complement (3)
// isn't in the map when we're processing the 3.
 
// Counter-example where self-complement SHOULD match:
// nums = [3, 3, 2, 4], target = 6
// i=0: num=3, complement=3, map={} → not found → add 3:0
// i=1: num=3, complement=3, map={3:0} → found! → return [0, 1] ✓

Edge Case 3: Negative Numbers Negative numbers work identically—the complement calculation handles them naturally: If nums[i] = -5 and target = 3, then complement = 3 - (-5) = 8 Edge Case 4: Zero Zero is a valid element and value: nums = [0, 4, 3, 0], target = 0 \to complement of 0 = 0 \to indices [0, 3] Edge Case 5: No Solution Always consider the possibility that no valid pair exists. The hash approach naturally returns after exhausting all elements.

Interview Tip

Always clarify assumptions with your interviewer: • Can there be multiple solutions? (Usually, assume exactly one) • Can the same element be used twice? (Usually, no) • Are there negative numbers? (Usually, yes—handle them) • What if no solution exists? (Return empty/null/throw?)

Two-Sum Variants

The Two-Sum pattern extends to numerous variants, each requiring slight modifications to the core algorithm. Variant 1: Two Sum with Sorted Input If the input is sorted, we can use the two-pointer technique instead of hashing—achieving O(1) space:

two_sum_sorted
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Two Sum II: Input is Sorted (Two Pointer Approach)
 * Time: O(n), Space: O(1)
 * 
 * Key insight: If sum is too small, move left pointer right
 *              If sum is too large, move right pointer left
 */
function twoSumSorted(nums: number[], target: number): [number, number] | null {
    let left = 0;
    let right = nums.length - 1;
    
    while (left < right) {
        const sum = nums[left] + nums[right];
        
        if (sum === target) {
            return [left, right];
        } else if (sum < target) {
            left++;  // Need larger sum, move left pointer right
        } else {
            right--; // Need smaller sum, move right pointer left
        }
    }
    
    return null;
}
 
// Example: nums = [2, 7, 11, 15], target = 9
// left=0 (2), right=3 (15): sum=17 > 9 → right--
// left=0 (2), right=2 (11): sum=13 > 9 → right--
// left=0 (2), right=1 (7): sum=9 = 9 → return [0, 1]
 
console.log(twoSumSorted([2, 7, 11, 15], 9)); // [0, 1]

Variant 2: Two Sum - Find All Pairs Instead of finding one pair, find all pairs that sum to target:

two_sum_all_pairs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Two Sum: Find All Pairs (by indices)
 * Time: O(n), Space: O(n)
 * 
 * Key insight: Store ALL indices for each value, not just one
 */
function twoSumAllPairs(nums: number[], target: number): [number, number][] {
    const result: [number, number][] = [];
    const valueToIndices = new Map<number, number[]>();
    
    // Build map: value → all indices where it appears
    for (let i = 0; i < nums.length; i++) {
        if (!valueToIndices.has(nums[i])) {
            valueToIndices.set(nums[i], []);
        }
        valueToIndices.get(nums[i])!.push(i);
    }
    
    // Find all pairs
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        const complementIndices = valueToIndices.get(complement) ?? [];
        
        for (const j of complementIndices) {
            // Only include pairs where i < j to avoid duplicates
            if (i < j) {
                result.push([i, j]);
            }
        }
    }
    
    return result;
}
 
// Example: nums = [1, 5, 3, 3, 3], target = 6
// Pairs: (1,5), (3,3), (3,3), (3,3) - but which indices?
console.log(twoSumAllPairs([1, 5, 3, 3, 3], 6));
// [[0,1], [2,3], [2,4], [3,4]]

Variant 3: Two Sum - Count Pairs (Unique Values) Count the number of unique pairs that sum to target:

two_sum_count
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Two Sum: Count Unique Value Pairs
 * Time: O(n), Space: O(n)
 * 
 * Count pairs of VALUES (not indices) that sum to target
 */
function countTwoSumPairs(nums: number[], target: number): number {
    const freq = new Map<number, number>();
    
    // Count frequency of each value
    for (const num of nums) {
        freq.set(num, (freq.get(num) ?? 0) + 1);
    }
    
    let count = 0;
    const counted = new Set<number>();
    
    for (const [num, numFreq] of freq) {
        const complement = target - num;
        
        // Skip if we've already counted this pair
        if (counted.has(num)) continue;
        
        if (num === complement) {
            // Self-pairing: need at least 2 of the same value
            // Number of pairs = C(n,2) = n*(n-1)/2
            if (numFreq >= 2) {
                count += (numFreq * (numFreq - 1)) / 2;
            }
        } else if (freq.has(complement)) {
            // Cross-pairing: every occurrence of num can pair with
            // every occurrence of complement
            count += numFreq * freq.get(complement)!;
            counted.add(complement); // Mark complement as counted
        }
        
        counted.add(num);
    }
    
    return count;
}
 
// Example: nums = [1, 5, 3, 3, 3], target = 6
// Pairs: 1+5=6 (1 pair), 3+3=6 (3 choose 2 = 3 pairs) = 4 total
console.log(countTwoSumPairs([1, 5, 3, 3, 3], 6)); // 4

Variant 4: Two Sum - Data Stream Design a data structure that supports adding numbers and checking for pairs:

two_sum_stream
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * TwoSum III - Data Structure Design
 * 
 * Supports:
 * - add(number): Add to the data structure
 * - find(target): Check if any pair sums to target
 */
class TwoSumStream {
    private freq = new Map<number, number>();
    
    /**
     * Add a number to the data structure
     * Time: O(1)
     */
    add(number: number): void {
        this.freq.set(number, (this.freq.get(number) ?? 0) + 1);
    }
    
    /**
     * Check if there exists any pair that sums to target
     * Time: O(n) where n is the number of unique values
     */
    find(target: number): boolean {
        for (const [num, count] of this.freq) {
            const complement = target - num;
            
            if (num === complement) {
                // Need at least 2 occurrences
                if (count >= 2) return true;
            } else {
                // Need complement to exist
                if (this.freq.has(complement)) return true;
            }
        }
        
        return false;
    }
}
 
// Usage
const ts = new TwoSumStream();
ts.add(1);
ts.add(3);
ts.add(5);
console.log(ts.find(4));  // true (1 + 3)
console.log(ts.find(7));  // false (no pair sums to 7... wait, 3+5=8, 1+5=6)
                          // Actually false - no pair sums to exactly 7
ts.add(4);
console.log(ts.find(7));  // true (3 + 4)

Beyond Two-Sum: Three-Sum and K-Sum

Two-Sum naturally extends to finding triplets (Three-Sum) and k-tuples (K-Sum). These problems combine the hash table insight with additional techniques. Three-Sum: Find Triplets Summing to Zero Given an array, find all unique triplets that sum to zero. This is a classic interview problem that combines Two-Sum with an outer loop:

three_sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Three Sum: Find All Unique Triplets
 * 
 * Approach: Sort + Two Pointers (more efficient than hash-based for this problem)
 * Time: O(n²), Space: O(1) excluding output
 * 
 * Key insight: Fix one element, then find Two-Sum on the remaining sorted array
 */
function threeSum(nums: number[]): number[][] {
    const result: number[][] = [];
    const n = nums.length;
    
    // Sorting enables two-pointer technique and easy duplicate skipping
    nums.sort((a, b) => a - b);
    
    for (let i = 0; i < n - 2; i++) {
        // Skip duplicates for the first element
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        
        // If smallest element is positive, no triplet can sum to 0
        if (nums[i] > 0) break;
        
        // Two-pointer Two-Sum for target = -nums[i]
        let left = i + 1;
        let right = n - 1;
        const target = -nums[i];
        
        while (left < right) {
            const sum = nums[left] + nums[right];
            
            if (sum === target) {
                result.push([nums[i], nums[left], nums[right]]);
                
                // Skip duplicates for second and third elements
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return result;
}
 
// Example
console.log(threeSum([-1, 0, 1, 2, -1, -4]));
// [[-1, -1, 2], [-1, 0, 1]]

Four-Sum and General K-Sum The pattern generalizes: for K-Sum, we reduce to (K-1)-Sum, which reduces to (K-2)-Sum, and so on until we reach Two-Sum:

k_sum
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * K-Sum: Generalized Solution
 * Time: O(n^(k-1)) for k-sum
 * 
 * Recursively reduce k-sum to (k-1)-sum until we reach 2-sum (two pointers)
 */
function kSum(nums: number[], target: number, k: number): number[][] {
    nums.sort((a, b) => a - b);
    return kSumHelper(nums, target, k, 0);
}
 
function kSumHelper(
    nums: number[], 
    target: number, 
    k: number, 
    start: number
): number[][] {
    const result: number[][] = [];
    const n = nums.length;
    
    // Base case: 2-sum with two pointers
    if (k === 2) {
        let left = start;
        let right = n - 1;
        
        while (left < right) {
            const sum = nums[left] + nums[right];
            
            if (sum === target) {
                result.push([nums[left], nums[right]]);
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        
        return result;
    }
    
    // Recursive case: reduce k-sum to (k-1)-sum
    for (let i = start; i <= n - k; i++) {
        // Skip duplicates
        if (i > start && nums[i] === nums[i - 1]) continue;
        
        // Pruning: if smallest k elements exceed target, break
        let minSum = 0;
        for (let j = 0; j < k; j++) minSum += nums[i + j];
        if (minSum > target) break;
        
        // Pruning: if nums[i] + largest (k-1) elements < target, skip
        let maxSum = nums[i];
        for (let j = 0; j < k - 1; j++) maxSum += nums[n - 1 - j];
        if (maxSum < target) continue;
        
        // Recurse: find (k-1)-sum for target - nums[i]
        const subResults = kSumHelper(nums, target - nums[i], k - 1, i + 1);
        
        for (const sub of subResults) {
            result.push([nums[i], ...sub]);
        }
    }
    
    return result;
}
 
// Example: 4-sum
console.log(kSum([1, 0, -1, 0, -2, 2], 0, 4));
// [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Summary: The Complement Lookup Pattern

Two-Sum is more than an interview problem—it's a template for recognizing a fundamental pattern in algorithm design. Let's consolidate the key insights:

Key Takeaways

•Transform 'find pair' into 'find complement' — This reframing converts O(n²) to O(n)
•One-pass is preferred — Build the map as you go; check before adding handles edge cases naturally
•The pattern applies to any binary relationship — Sum, difference, product, XOR—any operation where one value determines the other
•K-Sum reduces to Two-Sum — For k > 2, fix elements and reduce until you reach the base case
•Sorted inputs enable O(1) space — Two pointers work when order is guaranteed
•Edge cases matter — Duplicates, self-complements, and zeros require careful handling

Two-Sum Pattern Quick Reference
Relationship	Complement Formula	Example Problem
a + b = target	target - a	Two Sum, Three Sum
a - b = target	a - target or a + target	Pair with difference
a * b = target	target / a (if divisible)	Factor pairs
a XOR b = target	a XOR target	XOR queries
a mod b = target	Depends on context	Modular arithmetic

Page Complete

You now understand the Two-Sum pattern at a deep level—not as a single problem, but as a template for an entire class of complement-based algorithms. This mental model will help you recognize and solve pair-finding problems instantly. Next, we'll explore duplicate detection patterns.

Two-Sum and Pair Problems

The Gateway Problem

The Brute Force Baseline

The Hash Table Insight

Handling Edge Cases

Two-Sum Variants

Beyond Two-Sum: Three-Sum and K-Sum

Related Pair Problems

Summary: The Complement Lookup Pattern

Two-Sum and Pair Problems

The Gateway Problem

The Brute Force Baseline

The Hash Table Insight

Handling Edge Cases

Two-Sum Variants

Beyond Two-Sum: Three-Sum and K-Sum

Related Pair Problems

Summary: The Complement Lookup Pattern

Two-Sum and Pair Problems

The Gateway Problem

The Brute Force Baseline

The Hash Table Insight

Handling Edge Cases

Two-Sum Variants

Beyond Two-Sum: Three-Sum and K-Sum

Related Pair Problems

Summary: The Complement Lookup Pattern

There’s more to understand.

Two-Sum and Pair Problems

The Gateway Problem

The Brute Force Baseline

The Hash Table Insight

Handling Edge Cases

Two-Sum Variants

Beyond Two-Sum: Three-Sum and K-Sum

Related Pair Problems

Summary: The Complement Lookup Pattern

There’s more to understand.