LESSON 258 OF 414 · TWO POINTERS

Array Diff in Rust: 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

RUST · TWO POINTERS

Array Diff in Rust, explained

Problem overview

The function array_diff receives two vectors of integers, first and second. It must find one number from each whose absolute difference is as close to zero as possible, and return those two numbers as a vector, the one from first first. For first = [4, 1, 8] and second = [12, 3, 17] the answer is [4, 3], since |4 - 3| = 1 and no other pair is closer.

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

Approach: sort both, then sweep

Comparing every number of first with every number of second costs O(n · m). Sorting first makes a single pass enough.

Put a pointer i at the start of the sorted first and a pointer j at the start of the sorted second. Look at the pair (first[i], second[j]), record it if its difference is the best so far, and then move one pointer. Which one? The one at the smaller value. Suppose first[i] is smaller. Pairing it with any later element of second would only make the gap larger, because those elements are at least as big as second[j]. So first[i] has already met its best partner, and it can be retired. Moving the pointer at the larger value is the wrong choice, since the gap with the smaller one would then only grow.

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

The example, sorted, is [1, 4, 8] and [3, 12, 17]:

(1, 3): difference 2, the best so far. 1 is smaller, so i moves on.
(4, 3): difference 1, a new best. 3 is smaller, so j moves on.
(4, 12): difference 8, not better. 4 is smaller, so i moves on.
(8, 12): difference 4, not better. 8 is smaller, so i moves on and first is finished.

The best pair was [4, 3].

Step by step

Sort first with first.sort(). The parameters are declared mut in the starter code, which is what allows sorting them in place.
Sort second the same way. The pointer trick needs both in ascending order.
Declare the pointers. i and j are mutable usize values starting at 0usize, since vectors are indexed with usize.
Track the best difference. smallest_diff starts at i32::MAX, so the first pair examined replaces it.
Prepare the answer. result is a mutable Vec::new(). Its element type is inferred from the pair assigned to it later.
Loop while i < first.len() && j < second.len(). When either vector is used up, there are no more pairs to look at.
Measure. let diff = (first[i] - second[j]).abs();. The parentheses make abs() apply to the whole subtraction.
Record improvements. If diff < smallest_diff, update smallest_diff and set result = vec![first[i], second[j]]. The test is strict, so a later pair with the same difference doesn't replace the first one found.
Advance the smaller side. If first[i] < second[j], do i += 1.
Otherwise advance j. The else branch covers second[j] being smaller or equal. With equal values the difference is 0, already the best possible, so it doesn't matter which pointer moves.
Return. End with result, with no semicolon.

The solution in Rust

impl Solution {
    fn array_diff(mut first: Vec<i32>, mut second: Vec<i32>) -> Vec<i32> {
        first.sort();
        second.sort();
        let mut i = 0usize;
        let mut j = 0usize;
        let mut smallest_diff = i32::MAX;
        let mut result = Vec::new();
        while i < first.len() && j < second.len() {
            let diff = (first[i] - second[j]).abs();
            if diff < smallest_diff {
                smallest_diff = diff;
                result = vec![first[i], second[j]];
            }
            if first[i] < second[j] {
                i += 1;
            } else {
                j += 1;
            }
        }
        result
    }
}

Rust details worth knowing:

mut on parameters. mut first: Vec<i32> means the function owns the vector and may change it. The caller's vector was moved in, so sorting it is invisible to anyone else.
Type inference. Vec::new() alone doesn't say what it holds. The compiler works it out from the later assignment vec![first[i], second[j]] and from the return type, Vec<i32>.
abs() is a method. There is no free function abs(x). Because the subtraction is parenthesised, the method applies to its result and not just to second[j].
Reassigning result. Assigning a new vec! drops the old pair and stores the new one.
Stable sort and space. sort() is a stable sort that may use a temporary buffer. A strictly in-place sort of integers is sort_unstable(). For integers the final order is the same.

Complexity

Time: O(n log n). Sorting both vectors costs O(n log n + m log m). The sweep is linear, since each iteration moves one pointer forward, so at most n + m iterations run.

Space: O(1) beyond the sort. The sweep keeps two indices, the best difference and a two-element answer. With sort_unstable() the sort needs no extra buffer either, while sort() can use a temporary one.

Edge cases and common mistakes

Equal values in both vectors. [1, 5] and [5, 9] give [5, 5], a difference of 0.
Single elements. [10] and [3] give [10, 3]. The only pair is the answer.
Empty input. If either vector is empty, the loop never runs and the function returns an empty vector. The lesson's inputs are non-empty.
Negative numbers. [-7, 20] and [-3, 30] give [-7, -3]. The absolute value makes the sign irrelevant.
Order of the pair. The element from first is always listed first, wherever it sits numerically: [1, 6] and [4, 9] give [6, 4].
Overflow in the subtraction. The difference is computed in i32. With first = [-5, 2147483647] and second = [-1], the pair (2147483647, -1) wraps in an optimized build to a negative number, so abs() doesn't give a positive value and the wrong pair [2147483647, -1] is returned instead of [-5, -1]. In a debug build the subtraction panics. Computing the difference as i64 avoids both.
Moving the wrong pointer. Advancing the larger side skips candidates that could be better.

Testing

[4, 1, 8] and [12, 3, 17] give [4, 3].
[1, 5] and [5, 9] give [5, 5].
[10] and [3] give [10, 3].
[-7, 20] and [-3, 30] give [-7, -3].
[1, 6] and [4, 9] give [6, 4].

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

Start learning free