Problem overview
The method MinimumAbsDifference receives an int[] of distinct integers and returns a List<int[]>. Each element of the list is a pair [a, b] with a < b, taken from the input, where b - a equals the smallest difference between any two numbers in the array. The pairs must be listed in ascending order.
For [4, 2, 1, 3] the smallest gap is 1, and three pairs have it: [1, 2], [2, 3] and [3, 4]. For [1, 3, 6, 10, 15] the smallest gap is 2, found only in [1, 3]. For [3, 8, -10, 23, 19, -4, -14, 27] the smallest gap is 4, shared by [-14, -10], [19, 23] and [23, 27].
Approach: sort, then only neighbours matter
Comparing every pair of numbers costs O(n²), and the constraints allow up to 100,000 numbers. Sorting avoids that. In a sorted array, if two numbers are not adjacent, there is at least one number between them, and the gaps from it to each of the two are both smaller than the gap between the two. So a non-adjacent pair can never have the minimum difference, and only neighbouring pairs need to be examined.
Sorting also gives the output order for free. Walking the sorted array from left to right produces pairs [nums[i - 1], nums[i]] whose first elements ascend, and the statement asks for exactly that order. Since the values are distinct, every gap is positive and each pair satisfies a < b.
The scan keeps the smallest gap seen so far, minDiff, and the list of pairs that have it. A smaller gap discards the list and starts a new one. An equal gap appends to it. A larger gap is ignored.
Tracing the third example: the sorted array is [-14, -10, -4, 3, 8, 19, 23, 27], and the gaps between neighbours are 4, 6, 7, 5, 11, 4 and 4. The first gap, 4, sets minDiff and adds [-14, -10]. The gaps 6, 7, 5 and 11 are larger and change nothing. The last two gaps tie at 4, so [19, 23] and [23, 27] are appended. No gap was smaller than 4, so the list is never reset.
Step by step
- Sort the array with
Array.Sort(nums), ascending and in place. - Initialise the best gap as
minDiff = nums[1] - nums[0], the gap of the first pair. Create an emptyList<int[]>namedminDiffPairs. - Loop over adjacent pairs with
ifrom 1. Each iteration looks at the pair ending at indexi. - Compute the gap
curDiff = nums[i] - nums[i - 1]. It is positive because the array is sorted and its values are distinct. - Check for a smaller gap:
curDiff < minDiff. - Replace the best. Inside the
if, setminDiff = curDiff, start a new empty list, and add the current pair asnew int[]{nums[i - 1], nums[i]}. - Check for a tie with
else if (curDiff == minDiff). - Append the pair in that branch.
- Return the list after the loop.
Notice that the list starts empty even though minDiff is initialised from the first pair. The first iteration, i = 1, computes the very same gap, so it takes the tie branch and adds the first pair.
The solution in C#
class Solution {
public List<int[]> MinimumAbsDifference(int[] nums) {
Array.Sort(nums);
int minDiff = nums[1] - nums[0];
List<int[]> minDiffPairs = new List<int[]>();
for (int i = 1; i < nums.Length; i++) {
int curDiff = nums[i] - nums[i - 1];
if (curDiff < minDiff) {
minDiff = curDiff;
minDiffPairs = new List<int[]>();
minDiffPairs.Add(new int[]{nums[i - 1], nums[i]});
} else if (curDiff == minDiff) {
minDiffPairs.Add(new int[]{nums[i - 1], nums[i]});
}
}
return minDiffPairs;
}
}
The C# details to notice:
- A list of arrays.
List<int[]>is a growable list whose elements are fixed-sizeint[]arrays.new int[]{x, y}creates a two-element array in one expression. - Arrays are reference types. Each pair is its own array object, so adding pairs to the list never makes them share storage.
- Replacing the list.
minDiffPairs = new List<int[]>()throws away the old pairs by pointing the variable at a fresh list.Clear()would work too. - The array is sorted in place. The caller's
numsis reordered by the call. - Integer overflow. The subtraction wraps silently in C# by default. With the lesson's value range of up to one million in magnitude, a difference is at most 2,000,000 and cannot overflow. For arbitrary
intvalues, such asint.MaxValueandint.MinValue, the difference could wrap to a wrong number, and computing it aslongwould be safer.
Complexity
Time: O(n log n). The sort dominates. The loop visits each adjacent pair once.
Space: O(1) beyond the output. Sorting is in place, and the only growing structure is the result list. In the worst case, such as [1, 2, 3, 4] where every gap ties, the result holds n - 1 pairs.
Edge cases and common mistakes
- Two elements.
[5, 1]sorts to[1, 5]and returns the single pair[1, 5]. - Fewer than two elements. The constraints rule it out. With one element,
nums[1]would throwIndexOutOfRangeException. - Ties. Forgetting the
else ifbranch keeps only the first pair with the smallest gap, which fails on[4, 2, 1, 3]. - Not resetting on a smaller gap. Keeping the old pairs when a smaller gap appears returns pairs whose gap is no longer minimal.
- Checking all pairs. It gives the same answer but is too slow for 100,000 elements.
- Returning pairs in the wrong order inside. Always write the smaller number first. Because the array is sorted,
nums[i - 1]is the smaller one.
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, 1]gives[[1, 5]].