1200. Minimum Absolute Difference
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 67.0%
Problem Breakdown
The problem requires finding all pairs of elements in an array that have the minimum absolute difference between them. The output should be a list of these pairs sorted in ascending order. The input is an array of distinct integers, and the constraints specify that the array length can range from 2 to (10^5), with each integer ranging from (-10^6) to (10^6).
Inputs:
- An array of distinct integers
arr.
Outputs:
- A list of pairs
[a, b]where:a < b- The absolute difference
b - ais the minimum among all possible pairs in the array.
Implicit Constraints/Edge Cases:
- The array has at least two elements.
- All elements are distinct.
- Negative numbers and large values are possible, so careful handling of differences is necessary.
- The output should be sorted by the pair values.
Intuition
A brute-force approach would involve checking all possible pairs in the array to find the minimum absolute difference. This approach has a time complexity of (O(n^2)), which is inefficient given the constraints ((n \leq 10^5)).
The key insight is that by sorting the array first, we can reduce the problem to a linear scan where we only need to compare adjacent elements. Sorting takes (O(n \log n)) time, and finding the minimum difference in a sorted array takes (O(n)) time. This combined approach is much more efficient.
Approach
- Sort the Array: Begin by sorting the array
arr. This will allow us to only consider adjacent elements when calculating differences. - Initialize Variables:
min_diff: Set it to a large value initially (e.g., infinity) to ensure any real difference found will be smaller.result: An empty list to store pairs with the minimum absolute difference.
- Find Minimum Difference:
- Iterate through the sorted array and calculate the difference between each pair of adjacent elements.
- If a new minimum difference is found, update
min_diffand resetresultto contain only this new pair. - If the current difference equals
min_diff, append the pair toresult.
- Return Result: The list
resultwill contain all pairs with the minimum absolute difference in ascending order.
Complexity Analysis
- Time Complexity: (O(n \log n)) due to the sorting step, where (n) is the length of the array.
- Space Complexity: (O(1)) for the additional variables used (excluding the space required for sorting and the output list).
Solution
def minimumAbsDifference(arr):
# Step 1: Sort the array
arr.sort()
# Step 2: Initialize variables
min_diff = float('inf')
result = []
# Step 3: Find the minimum absolute difference
for i in range(1, len(arr)):
diff = arr[i] - arr[i - 1]
if diff < min_diff:
min_diff = diff
result = [[arr[i - 1], arr[i]]]
elif diff == min_diff:
result.append([arr[i - 1], arr[i]])
# Step 4: Return the result
return result
Edge Cases Handled
- Sorted Array: If the array is already sorted, the algorithm will still work correctly as it only relies on adjacent elements.
- All Elements Same Difference: If all pairs have the same minimum difference, the algorithm will collect all such pairs in the
result. - Negative Numbers and Large Values: The sorting and difference calculation handle negative numbers and large values naturally without overflow issues.