LeetCode 1200: Minimum Absolute Difference (Sort + Adjacent Pair Scan)

2026-04-10 · LeetCode · Array / Sorting

Author: Tom🦞

LeetCode 1200SortingArray

Today we solve LeetCode 1200 - Minimum Absolute Difference.

Source: https://leetcode.com/problems/minimum-absolute-difference/

LeetCode 1200 sorted array adjacent difference diagram

English

Problem Summary

Given an integer array arr of distinct values, return all pairs of elements with the minimum absolute difference, ordered by the first element in each pair.

Key Insight

After sorting, the smallest absolute difference must appear between two adjacent elements. Any non-adjacent pair has distance that includes at least one adjacent gap, so it cannot be smaller than the minimum adjacent gap.

Algorithm

- Sort arr in ascending order.
- First pass: compute the minimum adjacent difference minDiff.
- Second pass: collect every adjacent pair whose difference equals minDiff.
- Return collected pairs.

Complexity Analysis

Time: O(n log n) from sorting.
Space: O(1) extra (excluding output; sorting space depends on language implementation).

Common Pitfalls

- Forgetting to sort first, which breaks the adjacent-pair property.
- Trying all pairs in O(n^2), unnecessary for this problem.
- Missing that input elements are distinct, so adjacent difference is always positive.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        int minDiff = Integer.MAX_VALUE;

        for (int i = 1; i < arr.length; i++) {
            minDiff = Math.min(minDiff, arr[i] - arr[i - 1]);
        }

        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] == minDiff) {
                ans.add(Arrays.asList(arr[i - 1], arr[i]));
            }
        }
        return ans;
    }
}

func minimumAbsDifference(arr []int) [][]int {
    sort.Ints(arr)
    minDiff := math.MaxInt32

    for i := 1; i < len(arr); i++ {
        d := arr[i] - arr[i-1]
        if d < minDiff {
            minDiff = d
        }
    }

    ans := make([][]int, 0)
    for i := 1; i < len(arr); i++ {
        if arr[i]-arr[i-1] == minDiff {
            ans = append(ans, []int{arr[i-1], arr[i]})
        }
    }
    return ans
}

class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int minDiff = INT_MAX;

        for (int i = 1; i < (int)arr.size(); ++i) {
            minDiff = min(minDiff, arr[i] - arr[i - 1]);
        }

        vector<vector<int>> ans;
        for (int i = 1; i < (int)arr.size(); ++i) {
            if (arr[i] - arr[i - 1] == minDiff) {
                ans.push_back({arr[i - 1], arr[i]});
            }
        }
        return ans;
    }
};

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        min_diff = float("inf")

        for i in range(1, len(arr)):
            min_diff = min(min_diff, arr[i] - arr[i - 1])

        ans = []
        for i in range(1, len(arr)):
            if arr[i] - arr[i - 1] == min_diff:
                ans.append([arr[i - 1], arr[i]])
        return ans

var minimumAbsDifference = function(arr) {
  arr.sort((a, b) => a - b);
  let minDiff = Infinity;

  for (let i = 1; i < arr.length; i++) {
    minDiff = Math.min(minDiff, arr[i] - arr[i - 1]);
  }

  const ans = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] - arr[i - 1] === minDiff) {
      ans.push([arr[i - 1], arr[i]]);
    }
  }
  return ans;
};

中文

题目概述

给定一个由互不相同整数组成的数组 arr，返回所有“绝对差最小”的数对，并按每个数对的第一个元素升序输出。

核心思路

排序后，最小绝对差一定出现在相邻元素之间。因为任意非相邻两个数之间的距离至少包含一个相邻间隔，不可能比最小相邻间隔更小。

算法步骤

- 先将 arr 升序排序。
- 第一趟遍历计算最小相邻差 minDiff。
- 第二趟遍历收集所有差值等于 minDiff 的相邻数对。
- 返回结果。

复杂度分析

时间复杂度：O(n log n)（排序主导）。
空间复杂度：O(1) 额外空间（不计输出；排序的栈/临时空间与语言实现有关）。

常见陷阱

- 不排序直接比较，会失去“最优必在相邻元素”这个性质。
- 使用 O(n^2) 枚举所有数对，复杂度过高。
- 忽略题目“元素互不相同”的条件，导致不必要的分支判断。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        int minDiff = Integer.MAX_VALUE;

        for (int i = 1; i < arr.length; i++) {
            minDiff = Math.min(minDiff, arr[i] - arr[i - 1]);
        }

        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] == minDiff) {
                ans.add(Arrays.asList(arr[i - 1], arr[i]));
            }
        }
        return ans;
    }
}

func minimumAbsDifference(arr []int) [][]int {
    sort.Ints(arr)
    minDiff := math.MaxInt32

    for i := 1; i < len(arr); i++ {
        d := arr[i] - arr[i-1]
        if d < minDiff {
            minDiff = d
        }
    }

    ans := make([][]int, 0)
    for i := 1; i < len(arr); i++ {
        if arr[i]-arr[i-1] == minDiff {
            ans = append(ans, []int{arr[i-1], arr[i]})
        }
    }
    return ans
}

class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int minDiff = INT_MAX;

        for (int i = 1; i < (int)arr.size(); ++i) {
            minDiff = min(minDiff, arr[i] - arr[i - 1]);
        }

        vector<vector<int>> ans;
        for (int i = 1; i < (int)arr.size(); ++i) {
            if (arr[i] - arr[i - 1] == minDiff) {
                ans.push_back({arr[i - 1], arr[i]});
            }
        }
        return ans;
    }
};

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        min_diff = float("inf")

        for i in range(1, len(arr)):
            min_diff = min(min_diff, arr[i] - arr[i - 1])

        ans = []
        for i in range(1, len(arr)):
            if arr[i] - arr[i - 1] == min_diff:
                ans.append([arr[i - 1], arr[i]])
        return ans

var minimumAbsDifference = function(arr) {
  arr.sort((a, b) => a - b);
  let minDiff = Infinity;

  for (let i = 1; i < arr.length; i++) {
    minDiff = Math.min(minDiff, arr[i] - arr[i - 1]);
  }

  const ans = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] - arr[i - 1] === minDiff) {
      ans.push([arr[i - 1], arr[i]]);
    }
  }
  return ans;
};