Two Sum

The Two Sum problem is one of the most well-known interview questions in algorithmic problem solving. While the task itself is simple—find two numbers that add up to a target—this question reveals whether a candidate understands hashing, lookup efficiency, and real-time decision making.

The beauty of this problem is in recognizing that a brute-force \( O(n²) \) approach can be transformed into a clean \( O(n) \) solution with the right data structure.

Problem

You are given an array of integers nums and an integer target. Your task:

Return the indices of the two numbers such that they add up to target.

Important details:

• You must return exactly one valid pair of indices.
• Each input is guaranteed to have exactly one solution.
• A number cannot be reused—each index can be used only once.
• You may return the answer in any order.

Example

Input:

nums = [2, 7, 11, 15]

target = 9

Output:

[0, 1]

Explanation:

nums[0] + nums[1] = 2 + 7 = 9.

Input:

nums = [3, 2, 4]

target = 6

Output:

[1, 2]

Input:

nums = [3, 3]

target = 6

Output:

[0, 1]

Solution

A naive approach would test all possible pairs, resulting in O(n²) time. But you can do far better by using a hash map to store numbers you’ve seen so far and their indices.

The central insight is simple:

For each number x, look for target – x in constant time.

Key idea

While scanning through the list:

For the current number x, compute its complement:

needed = target - x

1. If needed is already in the hash map, you’ve found the answer.
2. Otherwise, store x in the map and continue.

This transforms the problem into a single pass with \( O(1) \) lookups.

Why this works

The hash map ensures:

• You never have to rescan earlier elements.
• Each complement check happens in constant time.
• You respect the constraint of using each index only once.

This results in a clean \( O(n) \) solution—a hallmark of great interview code.

Algorithm outline

1. Initialize an empty hash map seen = {}.
2. Loop through the array with index i:
   • Let x = nums[i].
   • Compute needed = target - x.
   • If needed is in seen, return [seen[needed], i].
   • Otherwise, store seen[x] = i.
3. The problem guarantees a solution, so you will always return inside the loop.

Sample implementation (Python)

Alternative solutions

Sorting + two pointers (NOT valid for index problems)

You can sort the array and use a two-pointer technique to find the pair in \( O(n log n) \) time.
However:

• Sorting loses original index information unless you store it separately.
• The hash map solution is strictly better for this specific problem.

Brute force

Try all pairs; runs in \( O(n²) \).

Acceptable only when n is extremely small.

Interview insight

The Two Sum problem tests whether you can:

• Recognize when hashing eliminates a brute-force scan
• Use dictionary lookups effectively
• Think in terms of complements
• Write clean, efficient, and readable code under pressure

This problem is foundational, as many follow-up questions build on its pattern (e.g., “3Sum”, “Two Sum II”, “Subarray Sum Equals K”). Mastering it prepares you for an entire category of array + hash map challenges.