LESSON 256 OF 415 · TWO POINTERS

Array Diff in Swift: 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: |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 (not counting the sort itself and the returned pair).

STEP 1 OF 11

Guided

Ctrl + Enter to check

SWIFT · TWO POINTERS

Array Diff in Swift, explained

Problem overview

The method arrayDiff receives two arrays of integers, first and second. It must find one number from each array so that the absolute difference between them is as close to zero as possible, and return the two numbers as [fromFirst, fromSecond].

For first = [4, 1, 8] and second = [12, 3, 17], the pair 4 and 3 differs by 1, and no other pair does better, so the answer is [4, 3]. If either array is empty there is no pair, and the method returns an empty array.

Approach: sort both, then walk them together

Checking every pair is the obvious way, and it takes O(n * m) time. Sorting lets you do much better.

With both arrays in ascending order, put one index on the front of each. Look at the two values and the gap between them. Then decide which index to move:

If first[i] is the smaller value, the only way to shrink the gap is to raise it, so move i forward. Moving j would pair first[i] with something even larger, and the gap could only grow.
Otherwise second[j] is smaller or equal, and the same argument says to move j.

The smaller value never gets a better partner than the one it just had, because everything left in the other array is at least as large as the value it was compared with. So it is safe to throw it away. Each step discards one element, and the walk ends when either array is used up.

On the example, the sorted arrays are [1, 4, 8] and [3, 12, 17]. The steps are:

Pair	Difference	Best so far	Move
1 and 3	2	`[1, 3]`	`i`
4 and 3	1	`[4, 3]`	`j`
4 and 12	8	`[4, 3]`	`i`
8 and 12	4	`[4, 3]`	`i`

After the last step i is past the end of first, and the answer is [4, 3].

Step by step

Sort copies of both arrays. Parameters are constants in Swift, so the code declares new constants named first and second that hide the parameters, each set to sorted() of the original. sorted() returns a new array and leaves the caller's array alone.
Set two indices, i and j, both to 0.
Track the best so far. smallestDiff starts at Int.max, so the first pair always replaces it, and result starts as an empty array.
Loop while both indices are in range, so the walk stops as soon as either array is exhausted.
Compute the gap for the current pair: abs(first[i] - second[j]).
Record an improvement. If the gap is strictly smaller than smallestDiff, store it and set result to the current pair. Because the test is strict, a later pair with an equal gap doesn't replace the earlier one.
Move the index at the smaller value. When first[i] is smaller, advance i. In every other case, advance j.
Return result.

The solution in Swift

class Solution {
    func arrayDiff(_ first: [Int], _ second: [Int]) -> [Int] {
        let first = first.sorted()
        let second = second.sorted()
        var i = 0, j = 0
        var smallestDiff = Int.max
        var result = [Int]()
        while i < first.count && j < second.count {
            let diff = abs(first[i] - second[j])
            if diff < smallestDiff {
                smallestDiff = diff
                result = [first[i], second[j]]
            }
            if first[i] < second[j] {
                i += 1
            } else {
                j += 1
            }
        }
        return result
    }
}

Swift details worth knowing:

Shadowing a parameter. let first = first.sorted() is legal in Swift, because the new constant is declared in the method body's scope, and the right-hand side still refers to the parameter. From that line on, first means the sorted copy.
sorted() against sort(). sorted() returns a new array. sort() sorts in place and needs a var, which a parameter isn't.
Int.max is the largest Int, 9223372036854775807 on 64-bit platforms. Any real gap is smaller.
abs is a global function, so there is no Math. prefix or .abs() method.
Overflow traps. If the subtraction doesn't fit in an Int, for example Int.max - (-1), a Swift program crashes at run time instead of wrapping. Ordinary inputs are nowhere near that.
Arrays are values. The sorted copies are independent of the arguments.

Complexity

Time: O(n log n + m log m). The two sorts dominate. The walk afterwards advances one index per step and never goes back, so it takes at most n + m steps. With both arrays of size n, this is O(n log n).

Space: O(n + m). This version sorts copies, and a copy is as large as the original array. The walk itself needs only a few variables. Sorting the caller's arrays in place would avoid the copies, but then the method would have to change its inputs.

Edge cases and common mistakes

An empty array. The loop never runs, so arrayDiff([], [1]) returns [].
Equal values. For [5] and [5] the gap is 0 and the answer is [5, 5]. A gap of zero can't be beaten.
Negative numbers. [-4, -1] and [3, -2] give [-1, -2], a gap of 1. The absolute value handles the sign.
Ties between pairs. For [1, 2] and [2, 3] the pair [2, 2] wins with gap 0. When two pairs have the same gap, the one the walk meets first is kept.
Forgetting to sort. The reasoning for which index to move only holds on sorted data.
Moving the wrong index. Advancing the larger value can skip the best pair.
Swapped order in the answer. The first number must come from first and the second from second, even after sorting.

Testing

[4, 1, 8] and [12, 3, 17] give [4, 3].
[5] and [5] give [5, 5].
[10, 20] and [15, 25] give [10, 15], the first pair with gap 5.
[1, 2] and [2, 3] give [2, 2].
[] and [1] give [].

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

Start learning free