Week 1 · Arrays & Hashing

Two Sum

Given an integer array and a target, return the two indices whose values add to the target. The key interview constraint is that indices, not sorted values, are the answer.

Easy Arrays & Hashing Week 1 Practice runner

Frame the problem

One valid answer exists in the standard version.
Each element can be used at most once.
The input is not guaranteed to be sorted.
Negative values and duplicate values are allowed.

1. Reveal example inputs and outputs

Example 1

Input:

two_sum([
  2,
  7,
  11,
  15
], 9)

Output:

[
  0,
  1
]

Example 2

Input:

two_sum([
  10,
  -1,
  4,
  8
], 7)

Output:

[
  1,
  3
]

2. Brute force first

If you checked every pair, what is the nested-loop condition? Which part repeats work that a hash map could remember?

3. Reveal the insight ladder

At index i with value x, the only value that matters is target - x.
If target - x appeared earlier, the answer is already known.
A map from value to index is enough state because the output needs indices.
Check before inserting x so you cannot reuse the same element for both sides of the pair.

4. Dry run before code

nums = [2, 7, 11, 15], target = 9.
i = 0, x = 2, complement = 7, seen = {}. Not found, store {2: 0}.
i = 1, x = 7, complement = 2, seen has 2 at index 0. Return [0, 1].

5. Reveal final Python solution

def two_sum(nums, target):
    seen = {}
    for i, value in enumerate(nums):
        complement = target - value
        if complement in seen:
            return [seen[complement], i]
        seen[value] = i
    raise ValueError("no valid pair")

Complexity: Time O(n), because each number is processed once. Space O(n), because the map can hold most of the array.

Interview narration

I need a previous value that completes the current value to the target.
Because I need original indices, sorting would add extra bookkeeping and is unnecessary.
The invariant is: before each iteration, seen contains values from earlier indices only.

Common traps

Storing the current value before checking can reuse the same index when target is twice the value.
Returning the values instead of the indices.
Sorting the array and losing original positions.

Follow-up drills

1. How would this change if the input were sorted and you needed 1-indexed positions?

Use two pointers instead of a hash map: start left at 0 and right at n - 1. If the sum is too small, move left rightward; if too large, move right leftward; if equal, return [left + 1, right + 1]. The invariant is that every discarded pointer position cannot be part of a future answer because the array is sorted.

2. How would you return all unique pairs instead of one pair?

Sort a copy of the values or use counts. With sorting, move two pointers and skip duplicates after recording a pair. If original indices are required, keep value-to-indices buckets because sorting values alone loses position identity.

3. How would you scale the solution if the input stream arrives one value at a time?

Keep the same complement map idea. For each new value, check whether its complement already appeared; then store the new value and index. This supports online detection for the first pair without needing the full array in advance.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.