Smallest Difference Between Two Arrays: Two Pointers

You're given two non-empty integer arrays a and b. Pick one value from each so that the absolute difference between them is as small as it can be, and return that difference.

Examples

Input	Output	Why
`a = [1, 3, 15, 11, 2], b = [23, 127, 235, 19, 8]`	`3`	I'd say 11 and 8 are the pair you want, because no other two values get within 3 of each other.
`a = [10, 5, 40], b = [50, 90, 80]`	`10`	You can't get any closer than 40 and 50, since everything else in b is up at 80 or 90.
`a = [1, 2, 3], b = [3, 4]`	`0`	There's a 3 in both of them, and you can't really do better than a gap of 0.

Constraints

1 ≤ |a|, |b| ≤ 10⁵
−10⁶ ≤ a[i], b[j] ≤ 10⁶

Hints

Hint 1

If you try every pair it's O(|a| × |b|), so what do you think sorting both arrays would let you say about which pairs are even worth looking at?

Hint 2

Once they're both sorted you can put i at the start of a and j at the start of b, and if a[i] < b[j] I'd ask whether there's any point pairing a[i] with something later on in b.

Hint 3

There isn't, because everything later in b is even further away from a[i], so a[i] has had its best chance and i moves on (and it's the same thing for b[j] the other way round).

Where people lose marks

Moving the pointer on the bigger value. The gap can only grow that way, and you'll walk straight past the best pair.
Moving a pointer before you've updated the minimum, so that the last pair you look at before one array runs out never gets counted.
Computing a[i] − b[j] in 32 bits when the values can be near ±2 × 10⁹. Here they're capped at 10⁶ so it's safe, but I'd still say it.

Dry run on `[1,3,15,11,2],[23,127,235,19,8]`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 8

Step 1 / 8

a
10i2132113154
b
80j19123212732354
best∞
Both sorted: a is 1, 2, 3, 11, 15 and b is 8, 19, 23, 127, 235. A pointer goes at the start of each.
Step 2 / 8

a
10i2132113154
b
80j19123212732354
best7
The first pair, 1 and 8, are 7 apart, so that's the best you've got for now, and 1 is behind, so i moves on.
Step 3 / 8

a
1021i32113154
b
80j19123212732354
best6
2 and 8 are only 6 apart, which beats what you had, and a's pointer is on the smaller value and it's the one you'd move.
Step 4 / 8

a
102132i113154
b
80j19123212732354
best5
3 and 8 are only 5 apart, which beats what you had, and 3 is behind, so i moves on.
Step 5 / 8

a
102132113i154
b
80j19123212732354
best3
11 and 8 are only 3 apart, which beats what you had, and b's value is the smaller one now and j goes on to the next.
Step 6 / 8

a
102132113i154
b
80191j23212732354
best3
11 and 19 are 8 apart and that doesn't help, and 11 is behind, so i moves on.
Step 7 / 8

a
102132113154i
b
80191j23212732354
best3
15 and 19 are 4 apart and that doesn't help, and a's pointer is on the smaller value and it's the one you'd move.
Step 8 / 8

a
102132113154
b
8019123212732354
best3
One array has run out, so the smallest difference is 3.

How to think about it

Checking every pair is O(|a| × |b|), which is far too slow at 10⁵ each. Once both arrays are sorted you can walk a pointer along each one, the way you would to merge them, and keep the smallest gap you've seen.

The question at each step is which pointer to move. Say a[i] < b[j]. Everything after b[j] is at least as big, so it's at least as far from a[i], which means a[i] has already met the closest value it's ever going to meet in b. You can drop it and move i on. If b[j] is the smaller one the same thing's true of it and you move j. If they're equal the answer's 0 and you can stop.

I'd mention that this is the merge from merge sort, run with a running minimum in place of an output array. The sorts cost O(n log n) and the walk is linear.

Complexity. Time O(|a| log |a| + |b| log |b|) · Space O(1) extra (after in-place sorts)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def smallest_difference(a, b):
    a, b = sorted(a), sorted(b)
    i = j = 0
    best = float('inf')
    while i < len(a) and j < len(b):
        best = min(best, abs(a[i] - b[j]))
        if a[i] == b[j]:
            return 0
        if a[i] < b[j]:
            i += 1                      # a[i] has met its closest value in b
        else:
            j += 1                      # and the same for b[j]
    return best

#include <vector>
#include <algorithm>
#include <climits>

long long solve(std::vector<int> a, std::vector<int> b) {
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    size_t i = 0, j = 0;
    long long best = LLONG_MAX;
    while (i < a.size() && j < b.size()) {
        long long d = (long long)a[i] - b[j];
        best = std::min(best, d < 0 ? -d : d);
        if (a[i] == b[j]) return 0;
        if (a[i] < b[j]) ++i;           // a[i] has met its closest value in b
        else ++j;                       // and the same for b[j]
    }
    return best;
}

import java.util.Arrays;

class Solution {
    public long smallestDifference(int[] a0, int[] b0) {
        int[] a = a0.clone(), b = b0.clone();
        Arrays.sort(a);
        Arrays.sort(b);
        int i = 0, j = 0;
        long best = Long.MAX_VALUE;
        while (i < a.length && j < b.length) {
            best = Math.min(best, Math.abs((long) a[i] - b[j]));
            if (a[i] == b[j]) return 0;
            if (a[i] < b[j]) i++;       // a[i] has met its closest value in b
            else j++;                   // and the same for b[j]
        }
        return best;
    }
}

function smallestDifference(a, b) {
  a = a.slice().sort((x, y) => x - y);
  b = b.slice().sort((x, y) => x - y);
  let i = 0, j = 0, best = Infinity;
  while (i < a.length && j < b.length) {
    best = Math.min(best, Math.abs(a[i] - b[j]));
    if (a[i] === b[j]) return 0;
    if (a[i] < b[j]) i++;               // a[i] has met its closest value in b
    else j++;                           // and the same for b[j]
  }
  return best;
}

fn solve(a: &[i64], b: &[i64]) -> i64 {
    let (mut a, mut b) = (a.to_vec(), b.to_vec());
    a.sort();
    b.sort();
    let (mut i, mut j) = (0usize, 0usize);
    let mut best = i64::MAX;
    while i < a.len() && j < b.len() {
        best = best.min((a[i] - b[j]).abs());
        if a[i] == b[j] { return 0; }
        if a[i] < b[j] { i += 1; }      // a[i] has met its closest value in b
        else { j += 1; }                // and the same for b[j]
    }
    best
}

import Data.List (sort)

solve :: [Int] -> [Int] -> Int
solve a b = go (sort a) (sort b) maxBound
  where
    go (x : xs) (y : ys) best
      | x == y    = 0
      | x < y     = go xs (y : ys) best'   -- x has met its closest value in b
      | otherwise = go (x : xs) ys best'   -- and the same for y
      where best' = min best (abs (x - y))
    go _ _ best = best

Variants to try

If you're asked for the pair itself as well as the gap you'd keep the two values next to the running minimum and update all three together.
For three arrays, where you want to make max − min of one value from each as small as you can, you move the pointer on whichever of the three values is smallest.

Next problems

Easy10 min

The smallest difference between two arrays

Examples

Constraints

Hints

Where people lose marks

Dry run on `[1,3,15,11,2],[23,127,235,19,8]`

How to think about it

The solution, in six languages

Variants to try

Next problems

Move the zeros to the end

Keep each value at most twice

Merge two sorted arrays

Keep going

Move the zeros to the end

Keep each value at most twice

Merge two sorted arrays

The pattern behind it

The smallest difference between two arrays

Examples

Constraints

Hints

Where people lose marks

Dry run on [1,3,15,11,2],[23,127,235,19,8]

How to think about it

The solution, in six languages

Variants to try

Next problems

Move the zeros to the end

Keep each value at most twice

Merge two sorted arrays

Keep going

Move the zeros to the end

Keep each value at most twice

Merge two sorted arrays

The pattern behind it

Dry run on `[1,3,15,11,2],[23,127,235,19,8]`