Start learning free

LESSON 202 OF 344 · SORTING

Minimum Absolute Difference in Python: O(n log n) with Sorting

Practice O(n log n) Read the full explanation

Given an array of distinct integers nums, 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 nums
  • a < b
  • b - a equals to the minimum absolute difference of any two elements in nums

Example 1:

Input: nums = [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.

Example 2:

Input: nums = [1,3,6,10,15]
Output: [[1,3]]

Example 3:

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

Constraints:

  • 2 <= nums.length <= 105
  • -106 <= nums[i] <= 106

STEP 1 OF 9
    Ctrl + Enter to check

    PYTHON · SORTING

    Minimum Absolute Difference in Python, explained

    Problem overview

    The method minimumAbsDifference receives a list nums of distinct integers. It must return every pair [a, b] with a < b whose difference b - a is the smallest difference between any two elements. The pairs come back in ascending order.

    For nums = [3, 8, -10, 23, 19, -4, -14, 27] the smallest gap is 4. Three pairs have it: [-14, -10], [19, 23] and [23, 27]. Note that 23 appears in two pairs. A number can belong to more than one answer.

    Approach: sort, then compare neighbours

    Checking every pair costs O(n²), and the statement allows 100,000 numbers. Sorting removes most of that work. After sorting, the closest two numbers must be next to each other. If some pair a and c had another value b between them, then a and b would be closer than a and c, so a and c could never be the minimum.

    A small example makes it concrete. In the sorted list [1, 4, 6, 10], the pair 1 and 6 has gap 5, but 4 sits between them, and both 1 and 4 (gap 3) and 4 and 6 (gap 2) are smaller. Any pair that skips over a value loses to one of the pairs it skips over.

    So only n - 1 neighbouring pairs need checking. Sorting costs O(n log n) and the scan costs O(n).

    The sorted order also solves two output requirements for free. Each neighbouring pair is already smaller value first, and the pairs are produced from left to right, which is ascending order. No final sort or min/max is needed. The first version of this problem in the course checks every pair instead.

    Step by step

    1. Sort nums in place with nums.sort(). Everything after relies on this order.
    2. Start the record with the first neighbouring pair: minDiff = nums[1] - nums[0]. Then create an empty minDiffPairs list.
    3. Loop with i from 1 to the last index, so that nums[i - 1] and nums[i] are always a valid neighbouring pair.
    4. Compute curDiff as nums[i] - nums[i - 1]. In sorted order this can't be negative, so no abs is needed.
    5. If curDiff < minDiff, this pair is a new record.
    6. Replace the record and the list: set minDiff to curDiff and minDiffPairs to a list containing only [nums[i - 1], nums[i]]. Earlier pairs were less close than this one.
    7. Otherwise, if curDiff == minDiff, the pair ties with the record.
    8. Append [nums[i - 1], nums[i]] to minDiffPairs.
    9. Return minDiffPairs.

    Tracing [4, 2, 1, 3]: after sorting it is [1, 2, 3, 4]. The record starts at 1 with no pairs. At i = 1 the gap is 1, which ties with the record, so [1, 2] is appended. The same happens for [2, 3] and [3, 4], giving [[1, 2], [2, 3], [3, 4]].

    The solution in Python

    class Solution:
    def minimumAbsDifference(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        minDiff = nums[1] - nums[0]
        minDiffPairs = []
        for i in range(1, len(nums)):
            curDiff = nums[i] - nums[i - 1]
            if curDiff < minDiff:
                minDiff = curDiff
                minDiffPairs = [[nums[i - 1], nums[i]]]
            elif curDiff == minDiff:
                minDiffPairs.append([nums[i - 1], nums[i]])
        return minDiffPairs

    Python details worth knowing:

    • sort() works in place and returns None. That is why the code calls it on its own line instead of writing nums = nums.sort(), which would set nums to None. Use sorted(nums) if you want a new list and want to keep the original order.
    • The caller's list changes. Because the sort is in place, the list passed in ends up sorted. For [4, 2, 1, 3], the caller's list becomes [1, 2, 3, 4]. Copy first with sorted(nums) if that matters.
    • Python's sort is Timsort, with O(n log n) worst-case time.
    • range(1, len(nums)) starts at 1, so i - 1 is never negative. In Python a negative index would not raise an error but would silently read from the end of the list.

    Why the starting record is safe

    Starting minDiff at the first neighbouring gap means the loop can begin at i = 1, which compares the same pair again. That pair meets the tie branch and is appended, so it enters minDiffPairs exactly once. Starting from a very large number would also work, but this way needs no special constant.

    Complexity

    Time: O(n log n). The sort dominates. The loop makes n - 1 passes, each doing a subtraction and a comparison, which is O(n).

    Space: O(m) for the result, where m is the number of closest pairs and at most n - 1. The sort itself is in place, though Timsort may use up to O(n) temporary space internally.

    Edge cases and common mistakes

    • Two elements. [5, 1] sorts to [1, 5]. The starting record is 4, the loop runs once with a tie, and the answer is [[1, 5]].
    • Forgetting to sort first. On unsorted input, neighbours aren't necessarily close, and the negative differences would win the comparison.
    • Using a tie as a new record. With <= instead of < in the first test, a tie would wipe out the earlier pairs. The strict comparison keeps them and lets the elif handle ties.
    • Not discarding old pairs. When a smaller gap appears, the list must be replaced, or the result keeps pairs that aren't closest.
    • Overlapping pairs. Pairs such as [19, 23] and [23, 27] share an element, and both belong in the answer.
    • Fewer than two elements. The lesson's inputs always have at least two numbers. With a single element, nums[1] would raise IndexError.

    Testing

    • [4, 2, 1, 3] gives [[1, 2], [2, 3], [3, 4]].
    • [1, 3, 6, 10, 15] gives [[1, 3]].
    • [3, 8, -10, 23, 19, -4, -14, 27] gives [[-14, -10], [19, 23], [23, 27]].
    • [5, 1] gives [[1, 5]].
    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free