# The Perfect Match

> Two numbers walk into an interview...

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

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a list of integers and an integer target, find all unique pairs whose elements sum to the target. Each pair is a 2-element list [a, b] with a <= b. Return the list of pairs sorted lexicographically (by a, then b). Each pair appears at most once even if multiple instances exist in the input.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **two-sum pattern extended to unique pairs**. Interviewers check whether candidates can avoid duplicate pairs and maintain sorted output, adding complexity beyond the basic hash-map lookup.

---

### Break down the requirements

#### Step 1: Sort the input array

Sorting enables the two-pointer approach and automatically produces pairs in sorted order.

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

Left pointer starts at 0, right at the end. Move inward based on the sum comparison.

#### Step 3: Skip duplicate values

After finding a pair, advance both pointers past any duplicate values to avoid recording the same pair twice.

---

### The solution

**Sorted two-pointer with duplicate skipping**

```python
def find_pairs(nums, target):
    nums.sort()
    result = []
    left = 0
    right = len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            result.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 current_sum < target:
            left += 1
        else:
            right -= 1
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n log n) for sorting, plus O(n) for the two-pointer scan.
> 
> **Space:** O(k) where k is the number of unique pairs found.

> **Interviewers Watch For**
>
> How do you handle duplicates? The while loops that skip past repeated values after finding a match are the critical detail. Without them, pairs like `[1, 4]` could appear multiple times.

> **Common Pitfall**
>
> Using a hash set approach without tracking which pairs have already been added. This can produce duplicate pairs like `[2, 3]` and `[2, 3]` if 2 appears multiple times.

---

## Common follow-up questions

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

## 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). 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.