Problem overview
The method ArrayDiff receives two int[] arrays, first and second. It must return a pair of numbers, one taken from each array, whose absolute difference is as close to zero as possible.
For first = [4, 1, 8] and second = [12, 3, 17] the answer is [4, 3], because |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 arrays, then walk them together
The brute force compares every element of first with every element of second. That is O(n * m) comparisons, which is too slow.
Sorting changes the picture. With both arrays in ascending order, put one pointer at the start of each: i in first and j in second. Look at the current pair, then ask which pointer to move.
- If
first[i]is smaller thansecond[j], the gap can only shrink by raising the smaller side. Movingjforward would give a largersecond[j]and a bigger gap. So movei. - Otherwise
second[j]is the smaller one (or they are equal), so movej.
Pairs skipped this way cannot beat the best one seen so far, because the pointer that stayed behind would only pair with larger values on the other side. Each pointer moves forward at most once per element, so the sweep takes O(n + m). Sorting is O(n log n) and dominates, which matches the required bound.
Here is the sweep on the example. After sorting, first = [1, 4, 8] and second = [3, 12, 17]. The pair (1, 3) has difference 2, so it is recorded, and 1 is smaller, so i moves. The pair (4, 3) has difference 1, a new best. Now 3 is the smaller value, so j moves. The pair (4, 12) has difference 8, which is worse, and 4 is smaller, so i moves. The pair (8, 12) gives 4, which is also worse, and 8 is smaller, so i moves past the end of first and the loop stops. The best pair stays (4, 3).
Step by step
- Sort
firstandsecondin place.Array.Sortrearranges the array it is given and returns nothing. The sweep only works on ascending data. - Create two pointers
iandj, both starting at 0. - Track the best difference.
smallestDiffstarts atint.MaxValue, so the first pair examined always replaces it. - Keep the best pair in
result. It starts as an empty array, which is what is returned if an input is empty. - Loop while both pointers are in range. When either array is used up there is no pair left to look at.
- Measure the current pair with
Math.Abs(first[i] - second[j]). - Record an improvement. If the difference is strictly smaller than
smallestDiff, store it and build a new two-element array from the current pair. The strict comparison means that a later pair with an equal gap does not replace the earlier one. - Advance the smaller side. If
first[i]is smaller, incrementi. In theelsebranch incrementj, which also covers equal values. Their difference is 0, the best possible, so either move is safe. - Return
result.
The solution in C#
class Solution {
public int[] ArrayDiff(int[] first, int[] second) {
Array.Sort(first);
Array.Sort(second);
int i = 0, j = 0;
int smallestDiff = int.MaxValue;
int[] result = new int[]{};
while (i < first.Length && j < second.Length) {
int diff = Math.Abs(first[i] - second[j]);
if (diff < smallestDiff) {
smallestDiff = diff;
result = new int[]{first[i], second[j]};
}
if (first[i] < second[j]) {
i++;
} else {
j++;
}
}
return result;
}
}
Some C# points about this code:
Array.Sortis a static method. You call it asArray.Sort(first), notfirst.Sort(). It sorts the caller's array itself, so after the call the original order offirstandsecondis gone.new int[]{}creates an array of length 0.new int[]{first[i], second[j]}creates a new array each time an improvement is found, and the old one is discarded.Math.Absis capitalised like every C# method. It accepts anintand returns anint.- Integer overflow is silent.
first[i] - second[j]wraps around when the true difference does not fit in anint, for exampleint.MaxValue - (-1). For values of ordinary size this does not matter. If extreme values were possible, the subtraction would be done inlong.
Complexity
Time: O(n log n). Sorting each array costs O(n log n) and O(m log m). The loop moves one pointer per iteration and never moves one backward, so it runs at most n + m times. Sorting dominates.
Space: O(1) extra. The sorts happen in place, and the loop uses a few integers plus the two-element result. The sort itself may use some working memory, but nothing proportional to a copy of the input.
Edge cases and common mistakes
- An empty input. If either array is empty, the loop never runs and the method returns an empty array. For
first = []andsecond = [5]the result is[]. - Equal values. For
[5, 5]and[5]the first pair already has difference 0 and the result is[5, 5]. Nothing can improve on 0. - Ties between pairs. For
[1, 3]and[2], both(1, 2)and(3, 2)have difference 1. Because the update needs a strict<, the first pair found wins and the method returns[1, 2]. - Skipping the sort. The reasoning about moving the smaller pointer only holds for ascending arrays. On unsorted input the sweep can miss the best pair.
- Moving the wrong pointer. Advancing the larger side makes the next gap equal or bigger, and can skip the pair you wanted.
- Result order. The pair is always returned as
[element of first, element of second], as in the example's[4, 3].
Testing
first = [4, 1, 8],second = [12, 3, 17]gives[4, 3].first = [5, 5],second = [5]gives[5, 5].first = [1, 3],second = [2]gives[1, 2].first = [],second = [5]gives[].