029. Minimum-Difference Pairs

Why this mechanism works

For sorted values a<=b<=c, the nonadjacent difference c-a is at least either intervening difference. Consequently a globally minimum pair difference appears between neighbors. One pass over those neighbor edges can reset the output when a better gap is found or append when the gap ties.

State and boundaries

gap is the smallest edge difference examined. output contains every examined adjacent pair with that difference.

Protocol

1. Sort the values.
2. Examine adjacent pairs.
3. On a smaller gap replace gap and clear old answers.
4. On an equal gap append the pair.
5. Return output.

Visualization

sorted: 1--2--3--4
gaps:     1  1  1
all three adjacent pairs qualify

Python implementation

def minimum_difference_pairs(nums):
    values = sorted(nums)
    gap = float('inf')
    output = []
    for i in range(1, len(values)):
        difference = values[i] - values[i - 1]
        if difference < gap:
            gap = difference
            output = []
        if difference == gap:
            output.append((values[i - 1], values[i]))
    return output

Worked execution

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

L2 minimum_difference_pairs: values = sorted(nums)
nums=[4, 2, 1, 3]; values=[1, 2, 3, 4]

L3 minimum_difference_pairs: gap = float('inf')
nums=[4, 2, 1, 3]; values=[1, 2, 3, 4]; gap=inf

L4 minimum_difference_pairs: output = []
nums=[4, 2, 1, 3]; values=[1, 2, 3, 4]; gap=inf; output=[]

L5 minimum_difference_pairs: for i in range(1, len(values)):
nums=[4, 2, 1, 3]; values=[1, 2, 3, 4]; gap=inf; output=[]; i=1

L6 minimum_difference_pairs: difference = values[i] - values[i - 1]
nums=[4, 2, 1, 3]; values=[1, 2, 3, 4]; gap=inf; output=[]; i=1; difference=1

L8 minimum_difference_pairs: gap = difference
nums=[4, 2, 1, 3]; values=[1, 2, 3, 4]; gap=1; output=[]; i=1; difference=1

L11 minimum_difference_pairs: output.append((values[i - 1], values[i]))
nums=[4, 2, 1, 3]; values=[1, 2, 3, 4]; gap=1; output=[(1, 2)]; i=1; difference=1

L5 minimum_difference_pairs: for i in range(1, len(values)):
nums=[4, 2, 1, 3]; values=[1, 2, 3, 4]; gap=1; output=[(1, 2)]; i=2; difference=1

L11 minimum_difference_pairs: output.append((values[i - 1], values[i]))
nums=[4, 2, 1, 3]; values=[1, 2, 3, 4]; gap=1; output=[(1, 2), (2, 3)]; i=2; difference=1

L5 minimum_difference_pairs: for i in range(1, len(values)):
nums=[4, 2, 1, 3]; values=[1, 2, 3, 4]; gap=1; output=[(1, 2), (2, 3)]; i=3; difference=1

L11 minimum_difference_pairs: output.append((values[i - 1], values[i]))
nums=[4, 2, 1, 3]; values=[1, 2, 3, 4]; gap=1; output=[(1, 2), (2, 3), (3, 4)]; i=3; difference=1

L2 minimum_difference_pairs: values = sorted(nums)
nums=[1]; values=[1]

L3 minimum_difference_pairs: gap = float('inf')
nums=[1]; values=[1]; gap=inf

L4 minimum_difference_pairs: output = []
nums=[1]; values=[1]; gap=inf; output=[]

Why the solution is correct

A smaller observed gap invalidates all previous larger-gap answers, while equality adds another valid answer. The neighbor argument ensures that no nonadjacent pair has a smaller difference. The requested adjacent pairs are exactly those retained.

Time and space

O(n log n) time and O(n) space for sorting and output.

Common mistakes

Failing to clear on improvement retains nonminimal pairs. Duplicate values make zero a legitimate minimum difference.

Reasoning card

Transfer exercise

If the requested output is unique value pairs rather than adjacent occurrences, state how duplicate emission changes.