Problem overview
The method MinimumAbsDifference(int[] nums) receives an array of distinct integers. It must find the smallest absolute difference between any two elements and return every pair whose difference equals that minimum. Each pair is written [a, b] with a < b, and the list of pairs is sorted by a. The return type is List<int[]>: a list whose elements are two-element arrays.
For nums = {4, 2, 1, 3} the smallest difference is 1, reached by 1 and 2, 2 and 3, and 3 and 4. The answer is [[1, 2], [2, 3], [3, 4]]. For {1, 3, 6, 10, 15} the minimum is 2, and only [1, 3] reaches it.
Approach: compare every pair and keep the best
The brute-force plan has two parts. First, look at every pair of elements and compute its absolute difference. Second, keep track of the smallest difference seen so far and the pairs that reach it.
Whenever a pair's difference curDiff is smaller than the current minimum, we have a new record, and all pairs collected before it are now wrong: the list is replaced by one containing just the new pair. When curDiff equals the minimum, the pair is added to the list. A larger difference is ignored.
The pairs come out in the order the loops visit them, which isn't the order the problem wants, so one final sort by the smaller element puts them in ascending order. The pair [a, b] is written with Math.Min and Math.Max, so the smaller value is first regardless of where it sat in the array.
Checking all pairs costs O(n^2). This lesson uses that approach; a faster approach sorts the array first, because the closest pairs then sit side by side.
Step by step
- Initialise the minimum. Set
int minDifftoMath.Abs(nums[0] - nums[1]), the first pair's difference. This avoids needing a sentinel such as a huge number. DeclareminDiffPairsas a new emptyList<int[]>. - Outer loop.
int ipicks the first element of each pair. - Inner loop.
int jstarts ati + 1and picks the second element, so each pair is visited once. - Compute the difference.
int curDiff = Math.Abs(nums[i] - nums[j]); - New record. If
curDiff < minDiff, all earlier pairs are obsolete. - Replace. Inside that
if, setminDiff = curDiffand replace the list with a new one that holds only the pair[Math.Min(...), Math.Max(...)]. - Tie. An
else if (curDiff == minDiff)follows. - Add the tied pair. Append the same min-and-max pair to the list.
- Sort. After the loops, sort
minDiffPairsin place with a comparison lambda that orders two pairsaandbby their first element. - Return the list.
The solution in C#
class Solution {
public List<int[]> MinimumAbsDifference(int[] nums) {
int minDiff = Math.Abs(nums[0] - nums[1]);
List<int[]> minDiffPairs = new List<int[]>();
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
int curDiff = Math.Abs(nums[i] - nums[j]);
if (curDiff < minDiff) {
minDiff = curDiff;
minDiffPairs = new List<int[]> { new int[]{Math.Min(nums[i], nums[j]), Math.Max(nums[i], nums[j])} };
} else if (curDiff == minDiff) {
minDiffPairs.Add(new int[]{Math.Min(nums[i], nums[j]), Math.Max(nums[i], nums[j])});
}
}
}
minDiffPairs.Sort((a, b) => a[0] - b[0]);
return minDiffPairs;
}
}
The C# details:
- A list of arrays.
List<int[]>holdsint[]objects. The collection initialisernew List<int[]> { ... }creates a list that already contains the listed elements. - The first pair is counted by the loop.
minDiffstarts as the difference of the pair(0, 1)while the list is empty. When the loops reachi = 0, j = 1,curDiffequalsminDiff, so that pair is added through theelse ifbranch. - Sorting with a lambda.
List<T>.Sortaccepts aComparison<T>: a function that returns a negative number if the first argument comes first, a positive one if the second does, and 0 for a tie. Herea[0] - b[0]compares the pairs by their first elements. - Why the subtraction is safe here. The sort is not stable, so ties would come out in any order, but ties can't happen: the elements are distinct, and two different pairs with the same difference can't share their smaller element. Subtraction could overflow for values near the
intlimits, wherea[0].CompareTo(b[0])is the safer choice. Values of this size don't overflow. Math.Absandint.MinValue.Math.Absthrows anOverflowExceptionforint.MinValue. That can't happen here, because the difference of two small values is small.
Complexity
Time: O(n^2). The nested loops visit n(n - 1) / 2 pairs, each in constant time. The final sort costs O(k log k) for k tied pairs, and k is less than n, so the loops dominate.
Space: O(k) for the answer. Apart from the result list, which holds the k pairs, the method keeps a few integers. Replacing the list on a new record creates a new small list each time, but the old one becomes garbage, so memory doesn't accumulate.
With the problem's constraint of up to 100,000 elements, about five billion pairs is too slow in practice. That is why a faster solution sorts first: after sorting, the closest pairs must be neighbours.
Edge cases and common mistakes
- Two elements.
{5, 2}gives[[2, 5]]. The min and max put the smaller value first. - Several tied pairs.
{4, 2, 1, 3}gives three pairs. Forgetting theelse ifbranch would return only the first. - Negative values.
{3, 8, -10, 23, 19, -4, -14, 27}gives[[-14, -10], [19, 23], [23, 27]]. Differences are computed withMath.Abs, so signs don't matter. - Not clearing on a new record. Adding the new pair to the old list would mix pairs with different differences.
- Unordered pairs. Writing
new int[]{nums[i], nums[j]}would give[4, 2]instead of[2, 4]. - Skipping the final sort. The loops find pairs in array order, which isn't the required ascending order.
Testing
{4, 2, 1, 3}gives[[1, 2], [2, 3], [3, 4]].{1, 3, 6, 10, 15}gives[[1, 3]].{3, 8, -10, 23, 19, -4, -14, 27}gives[[-14, -10], [19, 23], [23, 27]].{5, 2}gives[[2, 5]].