# The Target Hunt

> Pairs that hit a target. Every one of them.

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

Domain: Python · Difficulty: medium · Seniority: L5

## Problem

Given a list of integers and integer target, return all unique [x, y] pairs with x != y (from distinct indices) summing to target, each index used in at most one pair. Preserve discovery order (greedy: sweep left-to-right, for each x pick the smallest index y > x such that x+y = target and y is unclaimed). Return pairs as lists.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **two-sum extension to find all unique pairs**, combining **sorting** with **two-pointer technique** or **hashmap tracking**. It probes handling of duplicates and the constraint that each element is used only once.

---

### Break down the requirements

#### Step 1: Sort the array

Sorting enables the two-pointer approach and simplifies duplicate skipping.

#### Step 2: Use two pointers from both ends

Start with left at the beginning and right at the end. If the sum equals the target, record the pair and skip duplicates.

#### Step 3: Skip duplicate values to ensure unique pairs

After finding a pair, advance both pointers past identical values to avoid reporting the same pair twice.

---

### The solution

**Sort then two-pointer scan with duplicate skipping**

```python
def find_pairs(nums: list, target: int) -> list:
    nums_sorted = sorted(nums)
    pairs = []
    left = 0
    right = len(nums_sorted) - 1
    while left < right:
        current_sum = nums_sorted[left] + nums_sorted[right]
        if current_sum == target:
            pairs.append((nums_sorted[left], nums_sorted[right]))
            left_val = nums_sorted[left]
            right_val = nums_sorted[right]
            while left < right and nums_sorted[left] == left_val:
                left += 1
            while left < right and nums_sorted[right] == right_val:
                right -= 1
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return pairs
```

> **Time and Space Complexity**
>
> **Time:** O(n log n) dominated by sorting. The two-pointer scan is O(n).
> 
> **Space:** O(n) for the sorted copy and result list.

> **Interviewers Watch For**
>
> The duplicate-skipping logic after finding a match. Without it, inputs like `[1, 1, 1, 5, 5, 5]` with target 6 would produce multiple copies of `(1, 5)`.

> **Common Pitfall**
>
> Using a set of seen values with the two-sum hashmap approach can miss pairs or produce duplicates if not implemented carefully. The sort-and-scan approach is more straightforward for the "all unique pairs" variant.

---

## Common follow-up questions

- What if you needed triplets instead of pairs? _(Tests extending to three-sum with an outer loop and inner two-pointer scan.)_
- What if elements could be used more than once? _(Tests modifying the pointer advancement to allow self-pairing.)_
- How would you handle this if the array was too large to sort in memory? _(Tests external sorting or partitioned hashmap approaches.)_
- What if you needed the original indices, not the values? _(Tests maintaining an index mapping through the sort step.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_target_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.