LESSON 228 OF 338 · TWO POINTERS

Array Diff in Go: Closest Pair with Sorting and Two Pointers

Practice O(n log n) Read the full explanation

Given two arrays of integers, find a pair of integers, one from each array, whose absolute difference is the closest to zero.

Example:

Input: first =[4, 1, 8],
       second = [12, 3, 17]

Output: [4, 3]
Explanation: abs(4-3) = 1 which is the closest to 0

Note:

Your algorithm should run in O(n log n) time and use O(1) extra space.

STEP 1 OF 11

Guided

Ctrl + Enter to check

Array Diff in Go, explained

Problem overview

The function arrayDiff receives two slices of integers, first and second. It must return a pair [a, b], with a from first and b from second, whose absolute difference |a - b| is as close to zero as possible. For first = [4, 1, 8] and second = [12, 3, 17] the answer is [4, 3], because |4 - 3| = 1 and no other pair is closer.

The statement allows O(n log n) time and O(1) extra space.

Approach: sort both, then sweep

Comparing every element of first with every element of second costs O(n * m). Sorting first makes a single linear sweep possible.

With both slices ascending, start a pointer i at the beginning of first and j at the beginning of second. Look at the pair first[i], second[j] and record its difference if it is the best so far. Then move the pointer that sits on the smaller value. Why: suppose first[i] is the smaller one. Every later element of second is at least second[j], so pairing first[i] with any of them gives a difference at least as large as the current one. The current first[i] has nothing more to offer, so it can be dropped, and the next, larger value of first is tried. The mirror argument applies when second[j] is smaller.

Each step discards one element, so the sweep takes at most n + m steps. The sorting, O(n log n), dominates the total.

On the example, the sorted slices are [1, 4, 8] and [3, 12, 17]. The pair (1, 3) has difference 2, so 1 is dropped. Then (4, 3) has difference 1, a new best, and 3 is the smaller value, so j moves. Then (4, 12) has difference 8 and 4 is dropped, (8, 12) gives 4, and 8 is dropped. The loop ends with the best pair [4, 3].

Step by step

Sort first with sort.Ints, which sorts a []int in place and returns nothing.
Sort second the same way. The pointer argument needs both slices ascending.
Create i and j at 0 in one := statement.
Create smallestDiff with the value math.MaxInt, the largest int, so that the first real difference replaces it.
Create result as an empty []int. It will be replaced whenever a closer pair appears.
Loop while both slices have elements: i < len(first) and j < len(second).
Compute diff as the absolute value of first[i] - second[j], using the abs helper.
Record a better pair. When diff < smallestDiff, update smallestDiff and set result to the new two-element slice.
Advance the smaller side. If first[i] < second[j], do i++.
Otherwise do j++. When the values are equal, the difference is 0, which cannot be beaten, so the choice doesn't matter.
Return result after the loop.

The solution in Go

func arrayDiff(first, second []int) []int {
    sort.Ints(first)
    sort.Ints(second)
    i, j := 0, 0
    smallestDiff := math.MaxInt
    result := []int{}
    for i < len(first) && j < len(second) {
        diff := abs(first[i] - second[j])
        if diff < smallestDiff {
            smallestDiff = diff
            result = []int{first[i], second[j]}
        }
        if first[i] < second[j] {
            i++
        } else {
            j++
        }
    }
    return result
}

The Go details worth a closer look:

Imports and the abs helper. The function uses the sort and math packages, so a standalone file needs both imports. abs is a separate integer function, because math.Abs works only on float64. A typical version is func abs(x int) int { if x < 0 { return -x }; return x }. The lesson supplies it for you.
sort.Ints changes the caller's slices. It sorts in place, so after the call the original first and second are reordered. With first = [4, 1, 8] the caller's slice becomes [1 4 8]. That is where the O(1) space comes from, since no copy is made, but copy the slices first if the order matters to you.
math.MaxInt. This constant is the largest int on the platform. It exists since Go 1.17.
A new slice for each improvement. result = []int{first[i], second[j]} replaces the old slice instead of editing it. Only two elements are stored, so the extra space stays constant.
Strict <. On a tie, the first pair found stays. For first = [1, 3] and second = [2], both (1, 2) and (3, 2) differ by 1, and the function returns [1 2].
Order inside the pair. The element from first always comes first, and the one from second second.

Complexity

Time: O(n log n). The two sorts cost O(n log n) and O(m log m). The sweep is linear, because every iteration advances one of the two pointers and they can advance at most n + m times in total.

Space: O(1). The sorting happens in place, and the function keeps a few integers and one two-element slice.

Edge cases and common mistakes

A shared value. If both slices contain the same number, the difference is 0. [5] and [5] give [5 5], and [1, 2] with [2, 3] gives [2 2].
Negative numbers. [-5, 10] with [-4, 20] gives [-5 -4]. Taking the absolute value of the difference makes the sign irrelevant.
An empty slice. The loop never runs and the function returns an empty slice.
Unsorted input. The pointer rule is only valid on sorted slices, which is why the first two steps sort.
Starting smallestDiff at 0. No difference could ever be smaller, so no pair would be recorded.
Using math.Abs on ints. It takes and returns float64, so the code wouldn't compile without conversions.
Moving the larger side. That only widens the gap, and it can skip the best pair.

Testing

[4, 1, 8] and [12, 3, 17] give [4, 3].
[5] and [5] give [5, 5].
[1, 3] and [2] give [1, 2].
[-5, 10] and [-4, 20] give [-5, -4].
[10] and [1, 2, 3] give [10, 3].

Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free