Smallest Difference

Tags

Smallest Difference

Category

Arrays

Difficulty

Medium

Problem Statement

Given two non-empty arrays of integers, find the pair of numbers (one from each array) whose absolute difference is closest to zero. Return the pair as an array. If there are multiple pairs with the same smallest difference, return any one of them.

Intuition

Sorting both arrays allows us to use a two-pointer approach. If the current element from the first array is smaller, advancing its pointer might bring us closer. If the current element from the second array is smaller, advancing its pointer might help instead. This greedy narrowing converges on the minimum difference.

Approach

  1. Sort both arrays.
  2. Initialize pointers i = 0 and j = 0 for array one and array two respectively.
  3. Track the smallest difference found so far and the corresponding pair.
  4. While both pointers are within bounds:
    • Compute the difference between arrayOne[i] and arrayTwo[j].
    • If the difference is 0, return the pair immediately (cannot improve).
    • If arrayOne[i] < arrayTwo[j], increment i.
    • Otherwise, increment j.
    • Update the best pair if the current absolute difference is smaller.
  5. Return the best pair.

Pseudocode

function smallestDifference(arrayOne, arrayTwo):
    sort(arrayOne)
    sort(arrayTwo)
    i = 0
    j = 0
    smallestDiff = infinity
    bestPair = []
    while i < length(arrayOne) and j < length(arrayTwo):
        first = arrayOne[i]
        second = arrayTwo[j]
        currentDiff = abs(first - second)
        if currentDiff == 0:
            return [first, second]
        if currentDiff < smallestDiff:
            smallestDiff = currentDiff
            bestPair = [first, second]
        if first < second:
            i += 1
        else:
            j += 1
    return bestPair

Time & Space Complexity

  • Time: O(n log n + m log m) — Dominated by sorting both arrays. The two-pointer traversal is O(n + m).
  • Space: O(1) — Beyond the space used for sorting, only a constant number of variables are needed.

Key Insights

  • Sorting transforms an O(n * m) brute-force problem into an O(n log n + m log m) problem.
  • The two-pointer technique works because advancing the pointer of the smaller element is the only way to potentially reduce the difference.
  • If a difference of 0 is found, it is optimal and we can return immediately.

Edge Cases

  • One or both arrays have a single element — the two-pointer still works correctly.
  • Arrays with all negative or all positive numbers — handled naturally.
  • Identical elements across arrays — difference of 0 is detected immediately.
  • Large value ranges — ensure no integer overflow when computing differences.

Linked mentions