# The Complement Hunt

> Every number is looking for its other half.

Canonical URL: <https://datadriven.io/problems/the_complement_hunt>

Domain: Python · Difficulty: easy · Seniority: L4

## Problem

Given a list of integers and a target integer, return a 2-element list [i, j] with i < j such that nums[i] + nums[j] = target. Exactly one solution exists.

## Worked solution and explanation

### Why this problem exists in real interviews

This is the classic **two-sum problem**, testing whether a candidate can trade space for time using a hash map. It is the most commonly asked warm-up problem and probes understanding of O(n) vs O(n^2) tradeoffs.

> **Trick to Solving**
>
> For each element, compute its complement (`target - current`). If the complement is already in a hash map of previously seen values, you have found the pair. This avoids the O(n^2) nested loop approach.

---

### Break down the requirements

#### Step 1: Build a lookup map as you iterate

Map each value to its index. Check for the complement before inserting the current element to avoid pairing an element with itself.

#### Step 2: Return indices in ascending order

The problem guarantees exactly one solution, so return `[earlier_index, current_index]` as soon as you find it.

---

### The solution

**Single-pass hash map complement lookup**

```python
def two_sum(nums: list, target: int) -> list:
    seen = {}
    for i in range(len(nums)):
        complement = target - nums[i]
        if complement in seen:
            result = [seen[complement], i]
            return result
        seen[nums[i]] = i
    return []
```

> **Time and Space Complexity**
>
> **Time:** O(n) single pass. Each lookup and insertion in the hash map is O(1) average.
> 
> **Space:** O(n) for the hash map storing up to n elements.

> **Interviewers Watch For**
>
> Do you immediately reach for the hash map approach, or do you start with a brute-force nested loop? The hash map solution is the minimum acceptable answer.

> **Common Pitfall**
>
> Inserting the current element into the map before checking for its complement. This can cause an element to pair with itself when the complement equals the current value.

---

## Common follow-up questions

- What if there could be multiple valid pairs? _(Tests returning all pairs, which requires continuing the scan instead of early return.)_
- What if the input is sorted? _(Tests the two-pointer technique as an O(1) space alternative.)_
- What if duplicates exist and both indices point to the same value? _(Tests that the hash map approach naturally handles this since you check before inserting.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_complement_hunt)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.