Start learning free

LESSON 201 OF 343 · SORTING

Minimum Absolute Difference in C++: 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

    C++ · SORTING

    Minimum Absolute Difference in C++, explained

    Problem overview

    The function minimumAbsDifference receives a vector of distinct integers, nums. It must find the smallest absolute difference between any two elements and return every pair [a, b], with a < b, whose difference equals it. The pairs must be listed in ascending order.

    For nums = [4, 2, 1, 3], the smallest difference is 1, reached by [1, 2], [2, 3] and [3, 4]. For [3, 8, -10, 23, 19, -4, -14, 27] the smallest difference is 4, and the answer is [[-14, -10], [19, 23], [23, 27]]. The vector can hold up to 100,000 numbers.

    Approach: sort, then compare neighbours

    The brute-force solution checks every pair, which is O(n²). For 100,000 elements that is about five billion pairs, too many.

    Sorting makes it much cheaper, because of one observation: in a sorted array, the closest pair is always adjacent. Suppose x < y < z in sorted order. Then z - x is larger than both y - x and z - y, so a pair with another element between them can't be a minimum. Only the n - 1 neighbouring pairs need checking.

    Sorting also solves the output requirements. In sorted order, each neighbouring pair is already [smaller, larger], and the pairs appear in increasing order, so no extra sorting of the result is needed. The numbers are distinct, so all differences are positive, and no absolute value is needed either.

    The scan keeps the best gap seen so far, minDiff, and a list of the pairs that achieve it. A smaller gap replaces the whole list. An equal gap is appended. A larger gap is ignored.

    On [4, 2, 1, 3] the sorted vector is [1, 2, 3, 4]. All three gaps are 1, so all three neighbouring pairs are kept.

    Step by step

    1. Sort ascending in place. Call sort on nums.begin() to nums.end(). After this, the closest pair must be adjacent.
    2. Seed the best gap. Set minDiff to nums[1] - nums[0], and declare an empty minDiffPairs. The constraints guarantee at least two elements.
    3. Loop over neighbours. The variable i starts at 1, so that i - 1 is always a valid index.
    4. Measure the gap. curDiff is nums[i] - nums[i - 1]. It is never negative in sorted order.
    5. Check for a new record. Test curDiff < minDiff.
    6. Reset on a record. Set minDiff to curDiff, and assign a nested brace list holding only the pair {nums[i - 1], nums[i]} to minDiffPairs. Assigning a brace list to a vector replaces its whole contents, which clears the old pairs in one step.
    7. Check for a tie. An else if tests curDiff == minDiff.
    8. Append on a tie. Push back {nums[i - 1], nums[i]}.
    9. Return minDiffPairs after the loop.

    The solution in C++

    class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int minDiff = nums[1] - nums[0];
        vector<vector<int>> minDiffPairs;
        for (int i = 1; i < nums.size(); i++) {
            int curDiff = nums[i] - nums[i - 1];
            if (curDiff < minDiff) {
                minDiff = curDiff;
                minDiffPairs = {{nums[i - 1], nums[i]}};
            } else if (curDiff == minDiff) {
                minDiffPairs.push_back({nums[i - 1], nums[i]});
            }
        }
        return minDiffPairs;
    }
};

    The C++ details worth knowing:

    • The first pair is not lost. minDiffPairs starts empty, although minDiff already holds the gap between nums[0] and nums[1]. The loop starts at i = 1, which measures that very same pair, finds curDiff == minDiff and appends it.
    • sort changes the caller's vector. The parameter is a reference, so after the call the caller's vector is sorted. Make a copy first if the original order matters.
    • Brace-list assignment. minDiffPairs = {{a, b}} builds one inner vector {a, b} and makes it the only element. push_back({a, b}) builds the inner vector and appends it.
    • Subtraction and overflow. With the constraint of values within one million in absolute value, nums[i] - nums[i - 1] is at most two million. If values could reach the int limits, the subtraction could overflow, and signed overflow is undefined behaviour. Using long long for the differences would avoid that.
    • Unsigned size. nums.size() is unsigned. The loop starts at 1 and the vector has at least two elements, so nothing wraps. On an empty vector, nums.size() - 1 would wrap to a huge number, a classic trap with unsigned sizes.

    Complexity

    Time: O(n log n). Sorting costs O(n log n) and the scan costs O(n), so sorting dominates.

    Space: O(n) for the result. The sort works in place, so the extra memory is the list of pairs. In the worst case, such as an evenly spaced sequence, every neighbouring pair is returned, which is n - 1 pairs.

    Edge cases and common mistakes

    • Two elements. [5, 1] sorts to [1, 5] and returns [[1, 5]].
    • Evenly spaced values. [1, 2, 3, 4] returns all three neighbouring pairs.
    • Negative numbers. Sorting handles them with no special case: [-14, -10] is a valid pair.
    • Checking only pairs involving the minimum. The best pair can be anywhere in the sorted order.
    • Forgetting to clear on a new record. Pairs from a larger gap would remain in the result.
    • Using two if statements. After a new record, minDiff equals curDiff, so a second plain if would append the same pair again.
    • Comparing non-neighbours. Looking at nums[i] - nums[i - 2] or any wider gap is wasted work. A pair with an element between them is never a minimum.

    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]].
    • [1, 2, 10, 11] gives [[1, 2], [10, 11]].
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free