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
Solution 1: Sorting + Binary Search
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$.
Python3
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
Java
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;
}
}
C++
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;
}
};
Go
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
}
TypeScript
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;
}
Swift
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
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$.
Python3
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
Java
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;
}
}
C++
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;
}
};
Go
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
}
TypeScript
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;
}