Practice/Amazon/Leetcode 1200. Minimum Absolute Difference

Leetcode 1200. Minimum Absolute Difference

CodingMust

Problem

Given an array of distinct integers, find all pairs of elements that have the minimum absolute difference among all possible pairs. Return the pairs in ascending order, where each pair is also sorted in ascending order.

The absolute difference between two numbers a and b is |a - b|.

Requirements

1. Identify the minimum absolute difference that can be achieved between any two distinct elements in the array
2. Find all pairs of elements that achieve this minimum difference
3. Return the pairs as a list of two-element lists
4. Each pair should be sorted in ascending order (smaller number first)
5. The output list should be sorted by the first element of each pair

Constraints

• 2 ≤ arr.length ≤ 105
• -106 ≤ arr[i] ≤ 106
• All elements in the array are distinct
• Time complexity should be O(n log n) or better
• Space complexity should be O(n) for the output (additional space should be O(1) if possible)

Examples

Example 1:

Input: arr = [4, 2, 1, 3] Output: [[1,2], [2,3], [3,4]] Explanation: After sorting, we get [1,2,3,4]. The minimum absolute difference is 1, which occurs between consecutive pairs (1,2), (2,3), and (3,4).

Example 2:

Input: arr = [1, 3, 6, 10, 15] Output: [[1,3]] Explanation: After sorting, the array remains [1,3,6,10,15]. The differences between consecutive elements are 2, 3, 4, and 5. The minimum is 2, occurring only between 1 and 3.

Example 3:

Input: arr = [3, 8, -10, 23, 19, -4, -14, 27] Output: [[-14,-10], [19,23], [23,27]] Explanation: After sorting: [-14,-10,-4,3,8,19,23,27]. The minimum difference is 4, occurring three times in the sorted array.