Problem overview
The method arrayDiff receives two arrays of numbers, first and second. It must find one number from each array so that the absolute difference between them is as close to zero as possible, and return that pair as [fromFirst, fromSecond].
In the example, first = [4, 1, 8] and second = [12, 3, 17]. The pair 4 and 3 differs by 1, and no other pair gets closer, so the answer is [4, 3].
The statement allows O(n log n) time and O(1) extra space.
Approach: sort both arrays, then sweep
Trying every pair costs O(n * m). Sorting first gives a much faster way. With both arrays ascending, keep one pointer in each. Look at the two current values and record their distance if it is the best so far. Then decide which pointer to move.
The rule is to move the pointer at the smaller value. Say first[i] is smaller than second[j]. Every later element of second is at least as large as second[j], so pairing first[i] with any of them would only widen the gap. The pair (first[i], second[j]) is the best that first[i] can ever do from here on, so first[i] is finished and i can advance. The same argument applies in the other direction.
Each iteration advances one pointer, so the sweep takes at most n + m steps. The sort costs O(n log n) and dominates. The space stays constant because the only extra data is two indices, a number and a two-element result. The sorts rearrange the input arrays in place, which is how the lesson stays within O(1) extra space.
On the example, the sorted arrays are [1, 4, 8] and [3, 12, 17]:
- 1 and 3 differ by 2. That is the best so far, so the result is
[1, 3]. The smaller value is 1, soiadvances. - 4 and 3 differ by 1. Better, so the result becomes
[4, 3]. The smaller value is now 3, sojadvances. - 4 and 12 differ by 8, which is worse. The smaller value is 4, so
iadvances. - 8 and 12 differ by 4. Worse again. 8 is smaller, so
iadvances and runs off the end offirst.
The loop stops, and the answer is [4, 3].
Step by step
- Sort
firstwith the comparator(a, b) => a - b. Without a comparator,sortcompares elements as strings, which puts 10 before 9. - Sort
secondthe same way. The pointer rule only works when both arrays are ascending. - Declare
iandj, both 0, one pointer per array. - Declare
smallestDiffasNumber.POSITIVE_INFINITY. Every real difference is smaller, so the first pair always replaces it. - Declare
resultas an emptynumber[]. The annotation is needed because an empty array literal gives TypeScript nothing to infer the element type from. - Loop while both pointers are in range. When either array is used up, no pair is left to examine.
- Compute
diffasMath.abs(first[i] - second[j]). - If
diff < smallestDiff, updatesmallestDiffand setresultto the current pair. The comparison is strict, so a later pair with the same distance doesn't replace the first one found. - Advance the pointer at the smaller value. If
first[i] < second[j], doi++. - Otherwise do
j++. This coverssecond[j]being smaller, and also equal values, where the difference is already 0 and either pointer may move. - Return
result.
The solution in TypeScript
class Solution {
arrayDiff(first: number[], second: number[]): number[] {
first.sort((a, b) => a - b);
second.sort((a, b) => a - b);
let i = 0, j = 0;
let smallestDiff = Number.POSITIVE_INFINITY;
let result: number[] = [];
while (i < first.length && j < second.length) {
let diff = Math.abs(first[i] - second[j]);
if (diff < smallestDiff) {
smallestDiff = diff;
result = [first[i], second[j]];
}
if (first[i] < second[j]) {
i++;
} else {
j++;
}
}
return result;
}
}
The TypeScript details worth a closer look:
- The comparator.
(a, b) => a - breturns a negative number whenashould come first, zero for equal values and a positive number otherwise. Plainsort()would give[1, 10, 9]for[10, 9, 1]. sortchanges the array it is called on. After the call, the caller'sfirstandsecondare sorted too. For the example,firstends up as[1, 4, 8]. Copy the arrays first if the original order matters, for example with[...first], at the price of extra space.Number.POSITIVE_INFINITYis a value of typenumberthat is greater than any other number. WritingInfinitymeans the same.- Replacing the pair.
result = [first[i], second[j]]builds a new two-element array each time. The old one is discarded, so the result always holds exactly one pair. - The order of the pair. The value from
firstalways comes first, whichever of the two is larger.
Complexity
Time: O(n log n). Sorting both arrays dominates. The sweep that follows moves one pointer per iteration and runs at most n + m times.
Space: O(1) extra. Apart from the in-place sorts, the method keeps two pointers, one difference and a result of two numbers. The sorting algorithm itself may use some working memory internally, which the statement doesn't count.
Edge cases and common mistakes
- An empty array. If either input is empty, the loop never runs and the method returns
[]. - Ties. For
first = [1, 3]andsecond = [2], both (1, 2) and (3, 2) are 1 apart. The strict<keeps the first pair found, so the result is[1, 2]. - A shared value. For
[1, 5]and[5, 9]the difference reaches 0 at the pair 5 and 5, and the method returns[5, 5]. - Negative numbers. The absolute value makes the distance independent of signs:
[-5, -1]and[2, -3]give[-5, -3]. - Sorting without a comparator. Values such as 10 and 9 end up in the wrong order, and the pointer rule stops being valid.
- Moving the wrong pointer. Advancing the pointer at the larger value can only widen the gap and skips pairs that might be better.
- Starting
smallestDiffat 0. No difference would ever be smaller than 0, soresultwould stay empty.
Testing
first = [4, 1, 8],second = [12, 3, 17]gives[4, 3].first = [1, 5],second = [5, 9]gives[5, 5].first = [10, 9],second = [1]gives[9, 1].first = [],second = [1]gives[].