#1200

Easy

LeetCode Problem Workspace

Minimum Absolute Difference

Find all pairs with the minimum absolute difference between two elements in an array, and return them in ascending order.

array sorting

Problem Statement

Given an array of distinct integers, your task is to find all pairs of elements with the minimum absolute difference between any two elements in the array. Each pair should be represented as an array [a, b], where a and b are the two elements in the pair. The output should be sorted by the pair values in ascending order.

For example, in the array [4, 2, 1, 3], the minimum absolute difference is 1, and the pairs with this difference are [[1, 2], [2, 3], [3, 4]]. The task is to return all such pairs, ordered correctly.

Examples

Example 1

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

Output: [[1,2],[2,3],[3,4]]

The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Example 2

Input: arr = [1,3,6,10,15]

Output: [[1,3]]

Example details omitted.

Example 3

Input: arr = [3,8,-10,23,19,-4,-14,27]

Output: [[-14,-10],[19,23],[23,27]]

Example details omitted.

Constraints

2 <= arr.length <= 105
-106 <= arr[i] <= 106

Solution Approach

Sort the Array

Start by sorting the input array in ascending order. This step ensures that the minimum absolute difference will be between consecutive elements, making it easier to identify pairs.

Iterate through Consecutive Pairs

After sorting, iterate through the array and compare each consecutive pair of elements. Calculate the absolute difference and keep track of the smallest difference encountered.

Collect All Pairs with Minimum Difference

Once the smallest difference is found, iterate through the array again to collect all pairs that match the minimum absolute difference, and store them in ascending order.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is dominated by the sorting step, which is O(n log n), where n is the number of elements in the array. After sorting, the iteration over the array is O(n), making the overall time complexity O(n log n). Space complexity is O(n) due to the storage needed for the result pairs.

What Interviewers Usually Probe

Assessing the candidate's approach to sorting and handling consecutive elements in the array.
Looking for clarity in the explanation of the solution's efficiency and correctness.
Evaluating how well the candidate optimizes both time and space complexity for large arrays.

Common Pitfalls or Variants

Common pitfalls

Not sorting the array before comparing pairs, which could result in incorrect outputs or inefficiency.
Failing to handle edge cases such as arrays with only two elements or arrays with larger numbers of elements.
Misunderstanding the requirement to return pairs in ascending order or returning them in an unsorted manner.

Follow-up variants

Consider the case when the array contains negative numbers or is already sorted.
What happens when there are multiple pairs with the same minimum absolute difference?
How would the solution change if the array were unsorted or if elements could repeat?

FAQ

How do I handle large arrays in the Minimum Absolute Difference problem?

Sorting the array ensures that you only need to check consecutive pairs, which makes the solution efficient even for large arrays.

Can the input array have repeated elements?

No, the problem specifies that the array contains distinct integers.

What is the time complexity of the solution for this problem?

The time complexity is O(n log n), dominated by the sorting step.

How do I ensure the output is in ascending order?

After sorting the array, iterate through it to collect pairs in ascending order automatically.

Are there any edge cases to consider for this problem?

Yes, edge cases like an array with only two elements or an array already sorted should be handled correctly.

terminal

Solution

Solution 1: Sorting

According to the problem description, we need to find the minimum absolute difference between any two elements in the array $arr$. Therefore, we can first sort the array $arr$, then traverse the adjacent elements to get the minimum absolute difference $mi$.

1

2

3

4

5

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        mi = min(b - a for a, b in pairwise(arr))
        return [[a, b] for a, b in pairwise(arr) if b - a == mi]

Continue Practicing

#1202 smallest string with swaps #1187 make array strictly increasing #1170 compare strings by frequency of the smallest character