The Perfect Match

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

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.

Two numbers walk into an interview...

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
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

Common follow-up questions