Two Sum

If there is one coding interview problem that every software engineer will encounter, it is Two Sum. Microsoft, Google, Amazon, Meta - virtually every major tech company has used it as a screening question at some point. It is also one of the most frequently asked problems on Firecode.io, where it is called "Two sum" - the same classic problem known as Two Sum on other interview platforms. Despite its apparent simplicity, Two Sum is a litmus test for how you think about data structures, time-space tradeoffs, and algorithm design.

TL;DR

Use a hash map to store each element's complement (target - n) as you iterate. For each new element, check if it already exists as a key in the map. If it does, you've found your pair. This runs in O(n) time and O(n) space, compared to the O(n^2) brute force of checking every pair.

Why This Problem Matters

Two Sum is the "Hello World" of algorithm interviews. It frequently appears as the opening question in technical screens because it cleanly separates candidates who default to brute force from those who reach for the right data structure. Nail it quickly and confidently, and you set the tone for the rest of the interview. Fumble the hash map approach, and you're already behind.

Beyond interviews, the complement pattern you learn here shows up everywhere: finding pairs with a given difference, checking if an array has duplicate values within a distance k, and building frequency counters for streaming data.

Understanding the Problem

Given: An array of integers and a target integer

Find: The indices of two numbers that sum up to the target

Return: An array [index1, index2] sorted in ascending order

Edge cases: If no pair is found, return an empty array

Here's the input we'll work with:

With target = 10, we need to find two elements that add up to 10. Looking at the array, 1 + 9 = 10, so the answer is [0, 1].

Constraints

• There will be at most one such pair in the input array
• If no pair is found, return an empty array
• The output array should be sorted in ascending order
• Target linear time and space complexity

The Brute Force Trap

The first approach that comes to mind is checking every pair: for each element, scan the rest of the array for its complement. This works, but it is O(n^2). For an array of 10,000 elements, that's 50 million comparisons. Interviewers expect you to recognize this immediately and propose something better.

The brute force checks every pair while the hash map finds the answer in at most n lookups. That difference matters when n grows large.

Solution Approach: The Complement Technique

The key insight is that for every number n in the array, there is exactly one other number that would complete the pair: target - n. We call this the complement. Instead of scanning the array for each complement, store complements in a hash map where lookups are O(1).

Here's the strategy:

1. Create an empty hash map
2. For each element n at index i, check if n exists as a key in the map
3. If yes, we've found the pair - the map holds the index of the other element
4. If no, store the complement target - n as a key with i as the value
5. If we exhaust the array without a match, return an empty array

Prefer a different language? Jump to solutions in other languages.

Step-by-Step Walkthrough

Let's trace through arr = [1, 9, 3, 4, 5] with target = 10.

Step 1: Process arr[0] = 1

Is 1 in the map? No, the map is empty. Store the complement: map[10 - 1] = map[9] = 0.

Step 2: Process arr[1] = 9

Is 9 in the map? Yes! The map says 9 was stored at index 0. We found our pair: indices [0, 1].

That's it. Two iterations, one hash map lookup, done. The hash map turned what would have been a nested loop into a single pass.

A Longer Example

Let's trace a case where the pair is not at the beginning. arr = [1, 2, 9, 11, 25] with target = 20.

The complement of 9 is 20 - 9 = 11, stored at index 2. When we reach index 3 with value 11, it matches the stored complement. Return [2, 3].

Implementation

import java.util.HashMap;
import java.util.Map;

public class Solution {
  public static int[] twoSum(int[] arr, int target) {
    // Create a HashMap to store the complement of each number and its index
    Map<Integer, Integer> map = new HashMap<>();

    // Iterate over the input array
    for (int i = 0; i < arr.length; i++) {
      int n = arr[i];

      // Check if the current number exists as a key in the map
      if (map.containsKey(n)) {
        // Found the pair - return the stored index and current index
        return new int[]{map.get(n), i};
      } else {
        // Store the complement with its index
        map.put(target - n, i);
      }
    }

    // No valid pair found
    return new int[]{};
  }
}

The code mirrors the walkthrough exactly. Each element either matches a stored complement or contributes its own complement to the map. The else branch is what makes this a single-pass algorithm: we build the lookup table as we go rather than constructing it upfront.

Complexity Analysis

Time Complexity: O(n)

We iterate through the array once. For each element, we perform one hash map lookup (containsKey) and potentially one insertion (put), both O(1) amortized. Total: O(n).

Space Complexity: O(n)

In the worst case, we store every element's complement in the map before finding a pair (or never finding one). With n elements, the map uses O(n) space. This is the classic time-space tradeoff: we spend O(n) memory to avoid the O(n^2) time of brute force.

Why Not Sort Instead?

Sorting the array to O(n log n) and using two pointers would save space, but it destroys the original indices. You'd need to track original positions somehow, adding complexity. For the standard Two Sum problem, the hash map approach is cleaner and faster.

Edge Cases Worth Testing

Duplicate Values

What happens with arr = [3, 3] and target = 6?

The complement of the first 3 is 6 - 3 = 3, stored with index 0. When we encounter the second 3, it matches. The order of "check then store" ensures we never compare an element to itself.

Negative Numbers

arr = [-1, -2, -3, -4, -5] with target = -8:

The complement of -3 is -8 - (-3) = -5. When we reach -5 at index 4, it matches. The hash map approach doesn't care about sign - it works uniformly with positive, negative, and zero values.

No Solution

For arr = [1, 2, 9, 11, 25] with target = 100, no pair sums to 100. The loop completes without finding a match, and we return an empty array. This is why the fallback return new int[]{} exists outside the loop.

Empty Array and Single Element

An empty array or single-element array can never contain a pair, so the loop body never executes (or executes once without a match), and we return an empty array.

Common Pitfalls

1. Storing the value instead of the complement: If you store map[n] = i instead of map[target - n] = i, your lookups will never match. The map must store what you're looking for, not what you've seen.

2. Checking after storing: If you store the complement first, then check, you'll match an element with itself. Always check before storing.

   // Wrong - can match element with itself
   map.put(target - n, i);
   if (map.containsKey(n)) { ... }
   
   // Correct - check first, then store
   if (map.containsKey(n)) { ... }
   else { map.put(target - n, i); }
   

3. Returning values instead of indices: Two Sum asks for indices, not the values themselves. Make sure your map stores indices.

4. Forgetting the no-solution case: Not all inputs have a valid pair. Always handle the fallback after the loop.

Interview Tips

When solving Two Sum in an interview:

1. Start with the brute force: Mention the O(n^2) nested loop approach, then immediately say "but we can do better with a hash map." This shows you understand the baseline before optimizing.

2. Explain the complement concept: "For each number, I know exactly what value would complete the pair. I can store that as a key in a hash map for O(1) lookup." This demonstrates your thought process.

3. Trace through an example: Pick a small array like [1, 9, 3] with target 10 and walk through each step. Interviewers value seeing you verify your logic before coding.

4. Discuss tradeoffs: "This uses O(n) extra space for the hash map, which is the standard tradeoff for reducing time from O(n^2) to O(n)." Acknowledging tradeoffs shows engineering maturity.

5. Handle follow-ups confidently:

   • "What if the array is sorted?" - Use two pointers for O(1) space
   • "What about Three Sum?" - Sort the array, fix one element, use two pointers for the remaining pair
   • "What if there are multiple pairs?" - Collect all pairs instead of returning early

Key Takeaways

• The complement technique (target - n) converts a search problem into a lookup problem, reducing time from O(n^2) to O(n) at the cost of O(n) space.
• Always check the map before storing the complement. Reversing this order can cause an element to match itself.
• The approach handles duplicates, negative numbers, and zero values uniformly because hash map lookups make no assumptions about the stored keys.
• Two Sum is the foundation for a family of problems including Three Sum, Two Sum II (sorted array), and K-Sum. Master the complement pattern here and it transfers directly.
• In interviews, lead with the brute force, pivot to the hash map, trace through an example, and discuss the time-space tradeoff. That sequence demonstrates structured problem-solving.

Related Problems

Once you're confident with Two Sum, try these problems that build on the same ideas:

• Find Pair Indices in Sorted Array - The sorted variant uses two pointers instead of a hash map for O(1) space
• Zero-Sum Triplet Finder - Extends Two Sum to three elements using sort plus two pointers
• Anagram Checker - Uses the same character counting technique as frequency-based Two Sum variants

These problems and hundreds more are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. Whether you're targeting Microsoft, Google, or your first engineering role, building fluency with fundamental patterns like the complement technique will serve you well.

Solutions in Other Languages

Python

from typing import List


class Solution:
    def two_sum(self, arr: List[int], target: int) -> List[int]:
        num_dict = {}
        for i, n in enumerate(arr):
            if n in num_dict:
                return [num_dict[n], i]
            else:
                num_dict[target - n] = i
        return []

Python's dictionary provides O(1) average-case lookups. The enumerate function gives both the index and value in a single iteration, making the code concise.

JavaScript

class Solution {
  twoSum(arr, target) {
    const map = new Map();
    for (let i = 0; i < arr.length; i++) {
      const n = arr[i];
      if (map.has(n)) {
        return [map.get(n), i];
      } else {
        map.set(target - n, i);
      }
    }
    return [];
  }
}

JavaScript's Map provides O(1) lookups and preserves insertion order, though order doesn't matter here.

TypeScript

class Solution {
  twoSum(arr: number[], target: number): number[] {
    const map = new Map<number, number>();
    for (let i = 0; i < arr.length; i++) {
      const n = arr[i];
      if (map.has(n)) {
        return [map.get(n)!, i];
      } else {
        map.set(target - n, i);
      }
    }
    return [];
  }
}

The non-null assertion ! on map.get(n) is safe here because we only enter the branch when map.has(n) is true.

C++

#include <unordered_map>
#include <vector>

class Solution {
public:
  std::vector<int> twoSum(std::vector<int> &arr, int target) {
    std::unordered_map<int, int> numMap;
    for (int i = 0; i < arr.size(); i++) {
      int num = arr[i];
      if (numMap.count(num)) {
        return std::vector<int>{numMap[num], i};
      } else {
        numMap[target - num] = i;
      }
    }
    return {};
  }
};

C++ uses std::unordered_map for O(1) average-case lookups. The count method returns 1 if the key exists, 0 otherwise.

Go

func TwoSum(arr []int, target int) []int {
    numMap := make(map[int]int)
    for i, num := range arr {
        if index, ok := numMap[num]; ok {
            return []int{index, i}
        }
        numMap[target-num] = i
    }
    return []int{}
}

Go's map type provides O(1) average-case lookups. The two-value assignment index, ok := numMap[num] is the idiomatic way to check for key existence.

Scala

import scala.collection.mutable

class Solution {
  def twoSum(arr: Array[Int], target: Int): Array[Int] = {
    val map = mutable.Map[Int, Int]()
    for (i <- arr.indices) {
      val n = arr(i)
      if (map.contains(n)) {
        return Array(map(n), i)
      } else {
        map.put(target - n, i)
      }
    }
    Array[Int]()
  }
}

Scala uses a mutable map here for O(1) insertion and lookup. The contains method checks for key existence before accessing the value.

Kotlin

class Solution {
    fun twoSum(arr: IntArray, target: Int): IntArray {
        val map = mutableMapOf<Int, Int>()
        for (i in arr.indices) {
            val n = arr[i]
            if (map.containsKey(n)) {
                return intArrayOf(map[n]!!, i)
            } else {
                map[target - n] = i
            }
        }
        return intArrayOf()
    }
}

Kotlin's mutableMapOf creates a LinkedHashMap under the hood. The !! operator asserts that the value is non-null, which is safe after the containsKey check.

Swift

import Foundation

class Solution {
    func twoSum(_ arr: [Int], _ target: Int) -> [Int] {
        var map = [Int: Int]()
        for i in 0..<arr.count {
            let n = arr[i]
            if let index = map[n] {
                return [index, i]
            } else {
                map[target - n] = i
            }
        }
        return [Int]()
    }
}

Swift's optional binding with if let is a clean way to both check for key existence and extract the value in one step.

Rust

use std::collections::HashMap;

impl Solution {
    pub fn two_sum(&self, arr: Vec<i32>, target: i32) -> Vec<i32> {
        let mut map: HashMap<i32, i32> = HashMap::new();
        for (i, &n) in arr.iter().enumerate() {
            if let Some(&stored_index) = map.get(&n) {
                return vec![stored_index, i as i32];
            } else {
                map.insert(target - n, i as i32);
            }
        }
        vec![]
    }
}

Rust uses if let Some(...) for pattern matching on the Option returned by map.get(). The i as i32 cast converts the usize index to match the return type.

C#

using System.Collections.Generic;

public class Solution {
    public int[] twoSum(int[] arr, int target) {
        var map = new Dictionary<int, int>();
        for (int i = 0; i < arr.Length; i++) {
            int n = arr[i];
            if (map.ContainsKey(n)) {
                return new int[]{map[n], i};
            } else {
                map[target - n] = i;
            }
        }
        return new int[]{};
    }
}

C# uses Dictionary<int, int> which provides O(1) average-case operations. The ContainsKey method checks for key existence before indexing.

Dart

class Solution {
  List<int> twoSum(List<int> arr, int target) {
    Map<int, int> map = {};
    for (int i = 0; i < arr.length; i++) {
      int n = arr[i];
      if (map.containsKey(n)) {
        return [map[n]!, i];
      } else {
        map[target - n] = i;
      }
    }
    return [];
  }
}

Dart's Map literal {} creates a LinkedHashMap. The null assertion ! on map[n] is safe after the containsKey check.

PHP

<?php

class Solution {
    public function twoSum(array $arr, int $target): array {
        $map = [];
        for ($i = 0; $i < count($arr); $i++) {
            $n = $arr[$i];
            if (array_key_exists($n, $map)) {
                return [$map[$n], $i];
            } else {
                $map[$target - $n] = $i;
            }
        }
        return [];
    }
}

PHP uses an associative array as the hash map. array_key_exists is preferred over isset because isset returns false for keys with a null value.

Ruby

class Solution
  def two_sum(arr, target)
    map = {}
    arr.each_with_index do |n, i|
      if map.key?(n)
        return [map[n], i]
      else
        map[target - n] = i
      end
    end
    []
  end
end

Ruby's Hash provides O(1) average-case lookups. The each_with_index method gives both the value and index, similar to Python's enumerate.