028. Closest Pair to Target

Interview · Download this solution · All solutions and shared helpers

Problem

Return a pair of values from distinct positions whose sum has minimum absolute difference from target. Sort a copy; return values in ascending order. If several pairs are equally close, return the first encountered by the specified inward two-pointer scan, starting at the extremes. Return None for fewer than two values.

Examples

Example 1

closest_pair([1, 4, 7, 10], 15)
=> (4, 10)

Four plus ten is closest, with error one.

Example 2

closest_pair([5], 10)
=> None

Two distinct positions are required.

Example 3

closest_pair([1, 2, 4, 5], 7)
=> (2, 5)

An exact pair ends the scan.

Reveal the worked solution and reasoning

Why this mechanism works

If the current sum is too small, any pair using the same left endpoint and a smaller right endpoint is no better. Discard that left endpoint. The symmetric argument discards the right endpoint when the sum is too large. Keep the best pair before discarding either candidate frontier.

State and boundaries

left and right are distinct candidate indices. best and error describe the best visited pair; strict replacement preserves the encounter tie rule.

Protocol

Sort a copy and handle fewer than two values.
Evaluate the extreme pair.
Replace best only on a smaller absolute error.
Move left for a small sum or right for a large sum.
Finish immediately on an exact sum.

Visualization

1 + 10 = 11 < 15 -> move left
4 + 10 = 14       -> best error 1
7 + 10 = 17 > 15 -> move right

Python implementation

def closest_pair(nums, target):
    values = sorted(nums)
    if len(values) < 2:
        return None
    left, right = 0, len(values) - 1
    best, error = None, float('inf')
    while left < right:
        total = values[left] + values[right]
        difference = abs(total - target)
        if difference < error:
            best = (values[left], values[right])
            error = difference
        if total == target:
            break
        if total < target:
            left += 1
        else:
            right -= 1
    return best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

closest_pair([1, 4, 7, 10], 15)

L2 closest_pair: values = sorted(nums)
nums=[1, 4, 7, 10]; target=15; values=[1, 4, 7, 10]

L5 closest_pair: left, right = 0, len(values) - 1
nums=[1, 4, 7, 10]; target=15; values=[1, 4, 7, 10]; left=0; right=3

L6 closest_pair: best, error = None, float('inf')
nums=[1, 4, 7, 10]; target=15; values=[1, 4, 7, 10]; left=0; right=3; best=None; error=inf

L8 closest_pair: total = values[left] + values[right]
nums=[1, 4, 7, 10]; target=15; values=[1, 4, 7, 10]; left=0; right=3; best=None; error=inf; total=11

L9 closest_pair: difference = abs(total - target)
nums=[1, 4, 7, 10]; target=15; values=[1, 4, 7, 10]; left=0; right=3; best=None; error=inf; total=11; difference=4

L11 closest_pair: best = (values[left], values[right])
nums=[1, 4, 7, 10]; target=15; values=[1, 4, 7, 10]; left=0; right=3; best=(1, 10); error=inf; total=11; difference=4

L12 closest_pair: error = difference
nums=[1, 4, 7, 10]; target=15; values=[1, 4, 7, 10]; left=0; right=3; best=(1, 10); error=4; total=11; difference=4

L16 closest_pair: left += 1
nums=[1, 4, 7, 10]; target=15; values=[1, 4, 7, 10]; left=1; right=3; best=(1, 10); error=4; total=11; difference=4

... 4 intermediate state changes omitted ...

L16 closest_pair: left += 1
nums=[1, 4, 7, 10]; target=15; values=[1, 4, 7, 10]; left=2; right=3; best=(4, 10); error=1; total=14; difference=1

L8 closest_pair: total = values[left] + values[right]
nums=[1, 4, 7, 10]; target=15; values=[1, 4, 7, 10]; left=2; right=3; best=(4, 10); error=1; total=17; difference=1

L9 closest_pair: difference = abs(total - target)
nums=[1, 4, 7, 10]; target=15; values=[1, 4, 7, 10]; left=2; right=3; best=(4, 10); error=1; total=17; difference=2

L18 closest_pair: right -= 1
nums=[1, 4, 7, 10]; target=15; values=[1, 4, 7, 10]; left=2; right=2; best=(4, 10); error=1; total=17; difference=2

Result: (4, 10). Four plus ten is closest, with error one.

closest_pair([5], 10)

L2 closest_pair: values = sorted(nums)
nums=[5]; target=10; values=[5]

Result: None. Two distinct positions are required.

Why the solution is correct

Each pointer move discards only pairs no better than the pair just evaluated on that frontier. Thus an optimal error is never lost without being represented by an equally good visited candidate. Exact error zero is globally optimal.

Time and space

O(n log n) time including sorting and O(n) space for the sorted copy.

Common mistakes

For [1,4,7,10] and target 15, (4,10) differs by one; (7,10) differs by two and is not an equally good answer. Tie behavior must be specified separately from optimal error.

Reasoning card

State: left and right are distinct candidate indices. best and error describe the best visited pair; strict replacement preserves the encounter tie rule.

Invariant: Discarded frontier pairs cannot improve in the required direction.

Decision to rehearse: Use order to decide which frontier must move.

Finish: Finish immediately on an exact sum

Transfer exercise

Require the lexicographically smallest optimal pair instead. Determine whether the existing early-exit and tie rules still suffice.