Skip to content

16.06. Smallest Difference

Description

Given two arrays of integers, compute the pair of values (one value in each array) with the smallest (non-negative) difference. Return the difference.

Example: 

Input: {1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}

Output:  3, the pair (11, 8)

Note:

  • 1 <= a.length, b.length <= 100000
  • -2147483648 <= a[i], b[i] <= 2147483647
  • The result is in the range [-2147483648, 2147483647]

Solutions

Thinking

Pick one value from each array to minimize the absolute difference. All pairs are \(O(nm)\).

For a fixed \(x\) in \(a\), only the closest value in \(b\) matters, which a sorted \(b\) answers by binary search.

Sort \(b\), then bisect_left each \(x\) and check the insertion point and its predecessor. Sorting plus \(n\) logarithmic probes dominate.

We can sort the array \(b\), and for each element \(x\) in array \(a\), perform a binary search in array \(b\) to find the element \(y\) closest to \(x\). Then, the absolute difference between \(x\) and \(y\) is the absolute difference between \(x\) and the closest element in \(b\).

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the length of array \(b\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def smallestDifference(self, a: List[int], b: List[int]) -> int:
        b.sort()
        ans = inf
        n = len(b)
        for x in a:
            j = bisect_left(b, x)
            if j < n:
                ans = min(ans, b[j] - x)
            if j:
                ans = min(ans, x - b[j - 1])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int smallestDifference(int[] a, int[] b) {
        Arrays.sort(b);
        long ans = Long.MAX_VALUE;
        for (int x : a) {
            int j = search(b, x);
            if (j < b.length) {
                ans = Math.min(ans, (long) b[j] - x);
            }
            if (j > 0) {
                ans = Math.min(ans, (long) x - b[j - 1]);
            }
        }
        return (int) ans;
    }

    private int search(int[] nums, int x) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int smallestDifference(vector<int>& a, vector<int>& b) {
        sort(b.begin(), b.end());
        long long ans = LONG_LONG_MAX;
        for (int x : a) {
            auto it = lower_bound(b.begin(), b.end(), x);
            if (it != b.end()) {
                ans = min(ans, (long long) *it - x);
            }
            if (it != b.begin()) {
                ans = min(ans, x - (long long) *prev(it));
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func smallestDifference(a []int, b []int) int {
    sort.Ints(b)
    var ans int = 1e18
    for _, x := range a {
        i := sort.SearchInts(b, x)
        if i < len(b) {
            ans = min(ans, b[i]-x)
        }
        if i > 0 {
            ans = min(ans, x-b[i-1])
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function smallestDifference(a: number[], b: number[]): number {
    b.sort((a, b) => a - b);
    let ans = Infinity;
    const search = (nums: number[], x: number): number => {
        let [l, r] = [0, nums.length];
        while (l < r) {
            const mid = (l + r) >> 1;
            if (nums[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    };
    for (const x of a) {
        const j = search(b, x);
        if (j < b.length) {
            ans = Math.min(ans, b[j] - x);
        }
        if (j > 0) {
            ans = Math.min(ans, x - b[j - 1]);
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    func smallestDifference(_ a: [Int], _ b: [Int]) -> Int {
        let sortedB = b.sorted()
        var ans = Int.max

        for x in a {
            let j = search(sortedB, x)
            if j < sortedB.count {
                ans = min(ans, abs(sortedB[j] - x))
            }
            if j > 0 {
                ans = min(ans, abs(x - sortedB[j - 1]))
            }
        }

        return ans
    }

    private func search(_ nums: [Int], _ x: Int) -> Int {
        var l = 0
        var r = nums.count
        while l < r {
            let mid = (l + r) / 2
            if nums[mid] >= x {
                r = mid
            } else {
                l = mid + 1
            }
        }
        return l
    }
}

Solution 2: Sorting + Two Pointers

Thinking

Per-element binary search still pays a log factor \(n\) times.

Sorting both arrays lets two pointers advance the smaller side, finishing in one linear pass after the sorts.

We can sort both arrays \(a\) and \(b\), and use two pointers \(i\) and \(j\) to maintain the current positions in the two arrays. Initially, \(i\) and \(j\) point to the beginning of arrays \(a\) and \(b\), respectively. At each step, we calculate the absolute difference between \(a[i]\) and \(b[j]\), and update the answer. If one of the elements pointed to by \(i\) and \(j\) is smaller than the other, we move the pointer pointing to the smaller element forward by one step. The traversal ends when at least one of the pointers goes beyond the array range.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the length of arrays \(a\) and \(b\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def smallestDifference(self, a: List[int], b: List[int]) -> int:
        a.sort()
        b.sort()
        i = j = 0
        ans = inf
        while i < len(a) and j < len(b):
            ans = min(ans, abs(a[i] - b[j]))
            if a[i] < b[j]:
                i += 1
            else:
                j += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int smallestDifference(int[] a, int[] b) {
        Arrays.sort(a);
        Arrays.sort(b);
        int i = 0, j = 0;
        long ans = Long.MAX_VALUE;
        while (i < a.length && j < b.length) {
            ans = Math.min(ans, Math.abs((long) a[i] - (long) b[j]));
            if (a[i] < b[j]) {
                ++i;
            } else {
                ++j;
            }
        }
        return (int) ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int smallestDifference(vector<int>& a, vector<int>& b) {
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        int i = 0, j = 0;
        long long ans = LONG_LONG_MAX;
        while (i < a.size() && j < b.size()) {
            ans = min(ans, abs(1LL * a[i] - 1LL * b[j]));
            if (a[i] < b[j]) {
                ++i;
            } else {
                ++j;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func smallestDifference(a []int, b []int) int {
    sort.Ints(a)
    sort.Ints(b)
    i, j := 0, 0
    var ans int = 1e18
    for i < len(a) && j < len(b) {
        ans = min(ans, abs(a[i]-b[j]))
        if a[i] < b[j] {
            i++
        } else {
            j++
        }
    }
    return ans
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function smallestDifference(a: number[], b: number[]): number {
    a.sort((a, b) => a - b);
    b.sort((a, b) => a - b);
    let [i, j] = [0, 0];
    let ans = Infinity;
    while (i < a.length && j < b.length) {
        ans = Math.min(ans, Math.abs(a[i] - b[j]));
        if (a[i] < b[j]) {
            ++i;
        } else {
            ++j;
        }
    }
    return ans;
}

Comments