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.

#1200

Easy

auto_awesome数组·排序

LeetCode 题解工作台

最小绝对差

给你个整数数组 arr ，其中每个元素都不相同。请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。每对元素对 [a,b ] 如下： a , b 均为数组 arr 中的元素 a b - a 等于 arr 中任意两个元素的最小绝对差示例 1：输入： arr = [4,2,1,3] 输…

数组排序

题目描述

给你个整数数组 arr，其中每个元素都 不相同。

请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。

每对元素对 [a,b] 如下：

a , b 均为数组 arr 中的元素
a < b
b - a 等于 arr 中任意两个元素的最小绝对差

示例 1：

输入：arr = [4,2,1,3]
输出：[[1,2],[2,3],[3,4]]

示例 2：

输入：arr = [1,3,6,10,15]
输出：[[1,3]]

示例 3：

输入：arr = [3,8,-10,23,19,-4,-14,27]
输出：[[-14,-10],[19,23],[23,27]]

提示：

2 <= arr.length <= 10^5
-10^6 <= arr[i] <= 10^6

lightbulb

解题思路

方法一：排序

根据题目描述，我们需要找出数组 $arr$ 中任意两个元素的最小绝对差，因此我们可以先对数组 $arr$ 排序，随后遍历相邻元素，得到最小绝对差 $mi$ 。

最后我们再遍历相邻元素，找出所有最小绝对差等于 $mi$ 的元素对。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是数组 $arr$ 的长度。

1

2

3

4

5

6

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]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1202 交换字符串中的元素 #1187 使数组严格递增 #1170 比较字符串最小字母出现频次