# The Perfect Match

> Two numbers walk into an interview...

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

Domain: Python · Difficulty: medium · Seniority: L4 · Asked in: Ripple

## Problem

You are reconciling a ledger export where `nums` holds integer amounts that can repeat and `target` is the figure two amounts must sum to. Find every distinct value-pair, each returned as `[a, b]` with the smaller amount first and the whole result ordered by first amount then second. A value that occurs many times still yields a given pair only once, and an equal-value pair such as `[3, 3]` counts only when that amount actually appears at least twice in `nums`.

## Example 1

Input:

```
nums = [1,2,3,4,5,6], target = 7
```

Output:

```
[[1,6],[2,5],[3,4]]
```

## Example 2

Input:

```
nums = [2,2,3,3,4], target = 6
```

Output:

```
[[2,4],[3,3]]
```

## Worked solution and explanation

### What this problem really is

Strip the ledger costume and this is the classic two-sum lookup with two twists that quietly separate people: collapse duplicate pairs, and hand the result back sorted. Anyone can spot that 1 and 6 make 7. The real tell is what a candidate does when the input holds two 2s against a target of 4: do you emit `[2, 2]` once, never, or twice? And the sharper trap is a lone value, like a single 0 with a target of 0, which must NOT pair with itself. Lose track of how many times each amount appears and the output balloons with repeats the grader rejects, or invents an equal-value pair that the input never supported.

---

### How to get there

#### Step 1: Sort first, on a copy

Sort a copy of the input. Sorting does double duty: it lets you walk the array from both ends, and it means the pairs come out in the exact order the prompt asks for, so there is no second sort at the end. Sort a copy, not the caller's list, so you never mutate an input the grader may reuse.

#### Step 2: Close in from both ends

Put one index at the start and one at the end. If the two values overshoot the target, pull the right index in; if they fall short, push the left index out. An equal-value pair only forms when two distinct positions hold that amount, so a single 0 never matches itself: there is no second 0 for the other index to land on.

#### Step 3: Step over the repeats

The moment you record a pair, advance past every repeat of both values before moving on. This is the line most people forget: without it, an input with three 2s and three 5s reports the same pair again and again.

---

### The solution

**Sorted scan with duplicate skipping**

```python
def sum_pairs(nums, target):
    nums = sorted(nums)
    pairs = []
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            pairs.append([nums[left], nums[right]])
            while left < right and nums[left] == nums[left + 1]:
                left += 1
            while left < right and nums[right] == nums[right - 1]:
                right -= 1
            left += 1
            right -= 1
        elif total < target:
            left += 1
        else:
            right -= 1
    return pairs
```

> **Cost**
>
> **Time:** O(n log n) for the sort, then a single O(n) sweep. Space: O(n) for the sorted copy plus O(k) for the k pairs returned. A set-based approach is also O(n) on the scan but spends more memory tracking seen values, and you still have to sort the pairs at the end, so it rarely beats this.

> **Interviewers watch for**
>
> The duplicate-skip loops are the whole interview. Watch for candidates who find the pairs correctly but emit `[2, 5]` three times because three 5s sat in the input. The fix is two lines, and forgetting them is the single most common way this answer fails.

> **Common pitfall**
>
> Reaching for a set of seen values without a plan for ordering or for equal-value pairs. A set loses how many times each amount appears, so it happily pairs a lone value with itself (reporting `[0, 0]` when a single 0 is present) and can emit the same pair twice when a value repeats. It also forces a separate sort of the output that the two-pointer version gets for free.

---

## Common follow-up questions

- What if you needed triplets that sum to the target? _(Tests the 3-sum approach: fix one element and run the two-pointer scan on the rest.)_
- What if duplicate pairs in the output were allowed? _(Tests removing the skip-duplicate logic.)_
- What if the input arrived as a stream and pairs had to be found online? _(Tests a streaming approach with a running set of seen values.)_
- What if you needed the pair closest to the target rather than exact? _(Tests tracking the minimum difference during the scan instead of an exact match.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_perfect_match)
- [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). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.