1200. Minimum Absolute Difference - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
You are given an array of distinct integers arr. Your task is to find all pairs of elements with the minimum absolute difference. A pair [a, b] is considered valid if:

( a < b )
The absolute difference ( b - a ) is equal to the smallest absolute difference among any two elements in the array.

Return a list of all such pairs in ascending order (sorted by the first number of each pair).

Examples:

Example 1:
- Input: arr = [4, 2, 1, 3]
- Output: [[1, 2], [2, 3], [3, 4]]
- Explanation:
  When the array is sorted, it becomes [1, 2, 3, 4].
  The differences between adjacent elements are:
  (2-1 = 1), (3-2 = 1), (4-3 = 1).
  The minimum absolute difference is 1, and the pairs with that difference are [1, 2], [2, 3], and [3, 4].
Example 2:
- Input: arr = [1, 3, 6, 10, 15]
- Output: [[1, 3]]
- Explanation:
  After sorting (though the array is already sorted), the differences are:
  (3-1 = 2), (6-3 = 3), (10-6 = 4), (15-10 = 5).
  The minimum absolute difference is 2, and the only pair with that difference is [1, 3].

Constraints:

$(2 \leq \text{arr.length} \leq 10^5)$
$(-10^6 \leq \text{arr}[i] \leq 10^6)$
All the integers in arr are distinct.

Hints

Sort the Array:
Since the array is unsorted, the minimum absolute difference between any two numbers will be among the differences between adjacent elements in the sorted order.
Scan Adjacent Pairs:
After sorting, iterate through the array to compute the difference between each pair of consecutive elements.
Track the Minimum:
Keep track of the smallest difference found while scanning the array. Then, make a second pass (or build the result as you go) to collect all pairs that have that difference.
Return Sorted Pairs:
Because the sorted order guarantees ( a < b ) in every adjacent pair, simply returning the pairs in the order you encounter them will satisfy the output requirements.

Approaches

Approach 1: Sorting and Scanning Adjacent Elements

Sort the Array:
Sort arr in ascending order.
Compute Differences:
Iterate over the sorted array and compute the difference between each adjacent pair.
Track Minimum Difference:
Update a variable min_diff with the smallest difference found.
Collect Pairs:
On a subsequent pass (or during the same iteration), collect all pairs ([arr[i], arr[i+1]]) where the difference equals min_diff.
Return Result:
Return the list of pairs.

Time Complexity: $(O(n \log n))$ due to sorting, then (O(n)) for scanning.
Space Complexity: (O(n)) for the output (ignoring the space used by the sorting algorithm).

Approach 2: Using a One-Pass Collection

You can combine the scanning and collection steps in one pass once the array is sorted. As you iterate, update the minimum difference and clear or update the result list accordingly.

Code Implementations

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Step-by-Step Walkthrough (Approach 1)

Let’s walk through an example step by step:

Example:
arr = [4, 2, 1, 3]

Sort the Array:
Sorted array: [1, 2, 3, 4]
Initialize Variables:
- Set min_diff = ∞ (a very large number).
- Prepare an empty list result to store the pairs.
Scan Adjacent Pairs:
- Compare (1) and (2):
  Difference = (2 - 1 = 1).
  Since (1 < ∞), update min_diff to 1 and add pair [1, 2] to result (or plan to update later).
- Compare (2) and (3):
  Difference = (3 - 2 = 1).
  Since (1 == min_diff), add pair [2, 3] to result.
- Compare (3) and (4):
  Difference = (4 - 3 = 1).
  Again, (1 == min_diff); add pair [3, 4] to result.
Result:
The final list of pairs with the minimum difference is [[1, 2], [2, 3], [3, 4]].

Complexity Analysis

Time Complexity:
- Sorting: $(O(n \log n))$ .
- Scanning: $(O(n))$ .
- Overall: $(O(n \log n))$ .
Space Complexity:
- Output: (O(n)) in the worst-case scenario (if many pairs have the same minimum difference).
- Additional space for sorting depends on the sorting algorithm (typically (O(1)) to (O(n))).

Common Mistakes

Not Sorting the Array:
Without sorting, you might miss that the minimum difference can only occur between consecutive numbers in sorted order.
Off-by-One Errors:
Ensure you iterate from (i = 0) to $(i = \text{length} - 2)$ when comparing (arr[i]) and (arr[i+1]).
Incorrectly Handling the Result List:
Be careful to update the result list when a new minimum is found (clear previous pairs) versus when the difference is equal to the current minimum (append the pair).

Edge Cases

Array Length of 2:
With only two elements, simply return the pair $([min(arr[0], arr[1]), \max(arr[0], arr[1])])$ .
Large Array:
The solution must be efficient enough to handle up to $(10^5)$ elements.
Negative Values:
The array may contain negative integers; sorting and subtraction will still work correctly.

Minimum Absolute Difference in a BST:
Given a binary search tree, find the minimum absolute difference between any two nodes.
Closest Pair Problems:
There are similar problems where you need to find pairs with the smallest difference or closest values.