Sum Up a Pair in Array

By /

Can you find a pair in array that will sum up to particular number?

2026 Update: Two Sum — The Most Asked Coding Interview Question

Two Sum (find two numbers that add to a target) is the most commonly asked coding interview question. Master all four variants:

from typing import Optional

# Variant 1: Two Sum with hash map — O(n) time, O(n) space
def two_sum_hash(nums: list, target: int) -> Optional[tuple]:
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return None

# Variant 2: Two Sum on sorted array — O(n) time, O(1) space
def two_sum_sorted(nums: list, target: int) -> Optional[tuple]:
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return (nums[left], nums[right])
        elif s  list:
    seen = set()
    pairs = set()
    for num in nums:
        complement = target - num
        if complement in seen:
            pairs.add((min(num, complement), max(num, complement)))
        seen.add(num)
    return list(pairs)

# Variant 4: Closest pair to target
def two_sum_closest(nums: list, target: int) -> tuple:
    nums = sorted(nums)
    left, right = 0, len(nums) - 1
    best = (nums[left], nums[right])
    best_diff = abs(nums[left] + nums[right] - target)
    while left < right:
        s = nums[left] + nums[right]
        diff = abs(s - target)
        if diff < best_diff:
            best_diff = diff
            best = (nums[left], nums[right])
        if s  target:
            right -= 1
        else:
            return best
    return best

# Test
print(two_sum_hash([2, 7, 11, 15], 9))          # (0, 1)
print(two_sum_sorted([2, 3, 7, 11], 9))         # (2, 7)
print(two_sum_all_pairs([1, 2, 3, 4, 5], 6))    # [(1,5), (2,4)]
print(two_sum_closest([1, 3, 8, 10], 6))         # (3, 8) -- |11-6|=5, but (1,8)=|9-6|=3... (1,3)=|4-6|=2

Extension ladder:

  • 3-Sum: Sort + two-pointer inner loop. O(n²). Skip duplicate values. LeetCode #15
  • 4-Sum: Two outer loops + two-pointer inner. O(n³). LeetCode #18
  • k-Sum: Recursive reduction to (k-1)-Sum, base case = 2-Sum
  • Two Sum II (sorted input): Two pointers, O(1) space. LeetCode #167

💡Strategies for Solving This Problem

The Hash Map Classic

This is "Two Sum" - one of the most common interview questions ever. I've seen it at Google, Facebook, and Amazon. Everyone should know this cold.

The Problem

Given an array of numbers and a target sum, find two numbers that add up to the target. Return their indices.

Example: nums = [2, 7, 11, 15], target = 9
Answer: [0, 1] because nums[0] + nums[1] = 2 + 7 = 9

Naive Approach: Nested Loops

Try every pair: O(n²) time, O(1) space. Too slow.

Better: Hash Map

The key insight: When we see number x, we need to find (target - x).

Use a hash map to remember what we've seen:

  1. For each number, check if (target - number) is in the map
  2. If yes, we found the pair
  3. If no, add current number to map

O(n) time, O(n) space. Single pass.

Why Hash Map Wins

Hash map lookup is O(1). So checking "have we seen target - x?" is instant.

Without it, we'd need to search the array each time - that's O(n), making total O(n²).

Variation: Sorted Array

If array is sorted, you can use two pointers (left and right). Move them based on whether sum is too small or too large. O(n) time, O(1) space.

But if array isn't sorted, sorting first takes O(n log n), which is worse than hash map.

At Google

They asked me this as a warmup. Then asked: "What if there are multiple pairs?" Return all pairs or just one? "What if no solution exists?" Return empty array or null?

These clarifications matter. Always ask before coding.

Scroll to Top