Two Number Sum

Tags

Two Number Sum

Category

Arrays

Difficulty

Easy

Problem Statement

Given an array of distinct integers and a target sum, find and return a pair of numbers from the array that sum to the target. If no such pair exists, return an empty array. You may not use the same element twice.

Intuition

For every number x in the array, we need to check whether target - x also exists in the array. A brute-force approach checks every pair in O(n^2). By storing previously seen numbers in a hash set, we can look up the complement in O(1) per element, yielding an O(n) solution.

Approach

  1. Initialize an empty hash set.
  2. Iterate through each number in the array.
  3. Compute the complement: complement = target - current_number.
  4. If the complement exists in the hash set, return [complement, current_number].
  5. Otherwise, add the current number to the hash set.
  6. If no pair is found after the full iteration, return an empty array.

Pseudocode

function twoNumberSum(array, targetSum):
    seen = empty set
    for number in array:
        complement = targetSum - number
        if complement in seen:
            return [complement, number]
        seen.add(number)
    return []

Time & Space Complexity

  • Time: O(n) — We iterate through the array once, and each hash set lookup/insert is O(1) on average.
  • Space: O(n) — In the worst case, we store all n elements in the hash set before finding a pair (or not finding one).

Key Insights

  • Using a hash set trades space for time, reducing from O(n^2) to O(n).
  • An alternative O(n log n) approach: sort the array, then use two pointers from both ends moving inward. This uses O(1) extra space if sorting is done in-place.
  • The problem guarantees distinct integers, so we never accidentally match an element with itself.

Edge Cases

  • Array has fewer than two elements — no valid pair exists.
  • No pair sums to the target — return an empty array.
  • Negative numbers in the array — the complement logic handles negatives naturally.
  • Very large or very small integers — ensure no overflow when computing the complement.

Linked mentions