Sum Up a Pair in Array – Tech Interview Dot Org

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

💡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:

For each number, check if (target - number) is in the map
If yes, we found the pair
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.

✅Solution

Solution: Hash Map Approach

function twoSum(nums, target) {
    const map = new Map();  // value -> index

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (map.has(complement)) {
            return [map.get(complement), i];
        }

        map.set(nums[i], i);
    }

    return [];  // No solution found
}

// Tests
console.log(twoSum([2, 7, 11, 15], 9));  // [0, 1]
console.log(twoSum([3, 2, 4], 6));  // [1, 2]
console.log(twoSum([3, 3], 6));  // [0, 1]
console.log(twoSum([1, 2, 3], 10));  // [] (no solution)

Step-by-Step Example

nums = [2, 7, 11, 15], target = 9

i=0: nums[0] = 2
  complement = 9 - 2 = 7
  map.has(7)? No
  map.set(2, 0) → map = {2: 0}

i=1: nums[1] = 7
  complement = 9 - 7 = 2
  map.has(2)? Yes! map.get(2) = 0
  return [0, 1] ✓

Alternative: Two Pointers (If Sorted)

function twoSumSorted(nums, target) {
    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
        } else {
            right--;  // Need smaller sum
        }
    }

    return [];
}

// Test (array must be sorted!)
console.log(twoSumSorted([2, 7, 11, 15], 9));  // [0, 1]
console.log(twoSumSorted([2, 3, 4], 6));  // [0, 2]

Variation: Return All Pairs

function twoSumAllPairs(nums, target) {
    const map = new Map();
    const result = [];

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (map.has(complement)) {
            // Add all previous indices that match
            for (const index of map.get(complement)) {
                result.push([index, i]);
            }
        }

        // Store index in array (handle duplicates)
        if (!map.has(nums[i])) {
            map.set(nums[i], []);
        }
        map.get(nums[i]).push(i);
    }

    return result;
}

// Test
console.log(twoSumAllPairs([1, 1, 1, 1], 2));
// [[0,1], [0,2], [0,3], [1,2], [1,3], [2,3]]

Complexity Analysis

Approach	Time	Space	Notes
Nested loops	O(n²)	O(1)	Too slow
Hash map	O(n)	O(n)	Best for unsorted
Two pointers	O(n)	O(1)	Only if sorted
Sort + two ptr	O(n log n)	O(1)	Worse than hash map

Edge Cases

No solution: Return [] or null (clarify with interviewer)
Same element twice: [3, 3] with target 6 → works correctly
Multiple solutions: Return first found or all? (clarify)
Negative numbers: Works the same
Empty or single element: Return [] (can't make pair)

Common Mistakes

Using same element twice: Make sure i != j (hash map approach handles this)
Not checking map before adding: Check first, then add - otherwise you might match number with itself
Returning values instead of indices: Problem asks for indices!
Modifying array: Don't sort if you need original indices

Follow-Up: Three Sum

If asked about three numbers summing to target:

Fix one number, use two-sum on the rest: O(n²)
Can't do better than O(n²) for three sum