Minimum Absolute Difference
Asked at Walmart
Problem
Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference in ascending order. Sorting the array ensures that the minimum difference always occurs between adjacent elements, reducing the problem to a single pass.
Asked At
| Company | Difficulty | |
|---|---|---|
| Walmart | EASY | View all Walmart questions → |
How to Think About It
Brute force: compare every pair of elements, track the minimum absolute difference.
Sort the array first so that the minimum difference must be between adjacent elements.
After sorting, make one pass computing arr[i+1] - arr[i] to find the minimum diff.
Collect all pairs that achieve the minimum difference in a second pass.
Time O(n log n) for sorting, space O(1) excluding the output. Total time O(n log n).
Optimal Approach
Sort the array. Initialize minDiff to a large value. Iterate through adjacent pairs, updating minDiff whenever a smaller difference is found. In a second pass, collect all pairs whose difference equals minDiff. Sorting guarantees the minimum difference is between neighbors. Time complexity is O(n log n) due to sorting. Space is O(1) auxiliary.
What Trips People Up in Real Interviews
Confirm that all elements are distinct (simplifies the logic).
Ask whether the output order matters (ascending order of pairs).
Mention that after sorting, non-adjacent pairs cannot have a smaller difference.
Edge cases: array of size 2 (return that single pair), all pairs have same difference.
Use a list of pairs rather than a set to maintain sorted output order.
Solution Code
def minimumAbsDifference(arr):
arr.sort()
min_diff = float('inf')
for i in range(len(arr) - 1):
min_diff = min(min_diff, arr[i + 1] - arr[i])
result = []
for i in range(len(arr) - 1):
if arr[i + 1] - arr[i] == min_diff:
result.append([arr[i], arr[i + 1]])
return resultFrequently Asked Questions
What is the Minimum Absolute Difference problem?
Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference in ascending order. Sorting the array ensures that the minimum difference always occurs between adjacent elements, reducing the problem to a single pass.
How do you solve Minimum Absolute Difference?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Minimum Absolute Difference?
Minimum Absolute Difference is asked at Walmart. It is a easy difficulty problem.
What are common mistakes on Minimum Absolute Difference?
- Confirm that all elements are distinct (simplifies the logic).
- Ask whether the output order matters (ascending order of pairs).
- Mention that after sorting, non-adjacent pairs cannot have a smaller difference.
- Edge cases: array of size 2 (return that single pair), all pairs have same difference.
- Use a list of pairs rather than a set to maintain sorted output order.