Start learning free

LESSON 205 OF 338 · SORTING

Minimum Absolute Difference in Go: O(n log n) by 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

    GO · SORTING

    Minimum Absolute Difference in Go, explained

    Problem overview

    The function minimumAbsDifference receives a slice of distinct integers, nums, with at least two elements. It must find the smallest absolute difference between any two elements and return every pair [a, b] with a < b whose difference b - a equals that minimum. The pairs must come in ascending order.

    For nums = [4, 2, 1, 3], the smallest difference is 1, reached by [1, 2], [2, 3] and [3, 4]. For [1, 3, 6, 10, 15] the minimum is 2, and only [1, 3] reaches it.

    Approach: only neighbours can be the closest pair

    Comparing every pair costs O(n²), which is too slow for slices of up to 100,000 elements. Sorting makes it unnecessary. In a sorted slice, if two values x < z are not adjacent, some value y lies between them in the order. Then y - x and z - y are each no larger than z - x, so the non-adjacent pair can never beat the pairs formed with y. A pair of values at the minimum distance is therefore always a pair of neighbours. Since the values are distinct, both inner gaps are also strictly smaller than the outer one, so a non-adjacent pair can never even tie for the minimum.

    So the algorithm sorts, then looks at each adjacent pair once, keeping the best difference and the list of pairs that reach it. Because the slice is sorted, the pairs are produced already in ascending order, and each has a < b.

    On the third example, [3, 8, -10, 23, 19, -4, -14, 27], the sorted slice is [-14, -10, -4, 3, 8, 19, 23, 27]. The neighbour gaps are 4, 6, 7, 5, 11, 4 and 4. The minimum is 4, shared by [-14, -10], [19, 23] and [23, 27].

    Tracing the loop

    On the sorted third example, minDiff starts at 4 (from -10 minus -14), and minDiffPairs is empty. The first loop pass, i = 1, computes curDiff = 4. That is not smaller than 4, but it equals it, so the pair [-14, -10] is appended. This is why the loop starts at index 1 even though minDiff was already computed from the same pair: the pair itself still has to be recorded. The next three gaps (6, 7, 5) change nothing. The gap 11 changes nothing either. Then 4 appears twice more, appending [19, 23] and [23, 27].

    A slice where a smaller gap appears later shows the reset. For [1, 10, 11], the first gap is 9 and the pair [1, 10] is recorded. At i = 2, the gap is 1, which is smaller, so minDiff becomes 1 and the list is replaced by [[10 11]].

    Step by step

    1. Sort in place with sort.Ints(nums), so the closest pairs are adjacent.
    2. Initialise the best difference and the result. Declare minDiff := nums[1] - nums[0], the gap of the first pair, which is a real gap rather than a made-up "infinity". Declare minDiffPairs := [][]int{}, an empty slice of slices.
    3. Loop over the neighbours with i from 1 up to len(nums) - 1. Each pass looks at nums[i-1] and nums[i].
    4. Compute the gap in curDiff := nums[i] - nums[i-1]. It is never negative after sorting, so no absolute value is needed.
    5. Found a smaller gap. If curDiff < minDiff, update minDiff and replace the result with a new list holding only this pair. All earlier pairs were worse.
    6. Found an equal gap. In an else if curDiff == minDiff branch, append the pair to the list.
    7. Return minDiffPairs after the loop.

    The solution in Go

    func minimumAbsDifference(nums []int) [][]int {
    sort.Ints(nums)
    minDiff := nums[1] - nums[0]
    minDiffPairs := [][]int{}
    for i := 1; i < len(nums); i++ {
        curDiff := nums[i] - nums[i-1]
        if curDiff < minDiff {
            minDiff = curDiff
            minDiffPairs = [][]int{{nums[i-1], nums[i]}}
        } else if curDiff == minDiff {
            minDiffPairs = append(minDiffPairs, []int{nums[i-1], nums[i]})
        }
    }
    return minDiffPairs
}

    Go details:

    • [][]int is a slice whose elements are themselves slices. In the composite literal [][]int{{nums[i-1], nums[i]}}, the inner []int type is allowed to be omitted, which is why the reset line can use plain braces. When appending, you have to write []int{...} explicitly, since append is an ordinary function call, not a literal.
    • The result starts as an empty, non-nil slice. Because the first pair always sets the starting gap, at least one pair is always appended or kept, so the function never returns an empty list for valid input.
    • Each pair holds copies of the two integers. Changing nums later would not change the pairs.
    • sort.Ints reorders the caller's slice, and the file needs import "sort".

    Complexity

    Time: O(n log n). Sorting dominates. The loop is a single O(n) pass.

    Space: O(1) beyond the output. The scan keeps a few integers. The returned list of pairs can hold up to n - 1 pairs, which is required output and not working memory.

    Edge cases and common mistakes

    • Exactly two elements. [5, 1] sorts to [1, 5], the loop makes one pass and the result is [[1 5]].
    • Fewer than two elements. The solution reads nums[1] at the start, so a one-element slice panics with "index out of range [1] with length 1". The problem guarantees at least two.
    • Several pairs tied for the minimum. Use else if curDiff == minDiff to append them. Without it, only the first pair would be returned.
    • Forgetting to reset. When a smaller gap appears, the old pairs must be discarded. Appending instead of replacing would return pairs with a larger difference.
    • Starting minDiff at 0. With distinct values, no gap would ever be smaller than 0, so no pair would be recorded.
    • Comparing the original order. Without sorting, adjacent elements are not the closest ones: in [4, 2, 1, 3], the adjacent gaps are 2, 1 and 2, which miss the pair [3, 4].

    Small inputs to try in the editor above: [4, 2, 1, 3] should give [[1 2] [2 3] [3 4]], and [1, 3, 6, 10, 15] should give [[1 3]].

    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free