Minimum Absolute Difference — LeetCode 1200 Python Solution

The problem

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements. Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows a, b are from arr a < b b - a equals to the minimum absolute difference of any two elements in arr

This statement is abridged. Read the full problem on LeetCode.

Example

Input

arr = [4,2,1,3]

Output

[[1,2],[2,3],[3,4]]

Explanation

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

Python solution

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]

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1200. Minimum Absolute Difference is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems