Start learning free

LESSON 193 OF 343 · NESTED LOOPS & BRUTE FORCE

Minimum Absolute Difference in C++: Brute Force with Nested Loops

Practice O(n2) 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++ · NESTED LOOPS & BRUTE FORCE

    Minimum Absolute Difference in C++, explained

    Problem overview

    The function minimumAbsDifference receives a vector of distinct integers, nums. Among all pairs of elements, find the smallest absolute difference, then return every pair whose difference equals it. Each pair is written [a, b] with a < b, and the list of pairs is sorted in ascending order.

    For nums = [4, 2, 1, 3], the smallest difference is 1. The pairs with that difference are [1, 2], [2, 3] and [3, 4], so the result is [[1, 2], [2, 3], [3, 4]]. For [1, 3, 6, 10, 15] only the pair [1, 3] has the smallest difference, 2.

    Approach: try every pair

    This lesson is in the brute-force chapter, so the idea is the most direct one: look at every pair of positions, keep track of the best difference seen so far, and keep the list of pairs that achieve it.

    Whenever a pair has a difference smaller than the current best, two things happen. The best difference is replaced, and the list of collected pairs is thrown away, since those pairs are no longer minimal. The new pair starts a fresh list. Whenever a pair ties the best difference, it is appended to the list. A pair with a larger difference is ignored.

    To visit each pair once, the outer loop picks the first position i and the inner loop picks the second position j, starting at i + 1. This never pairs an element with itself and never looks at the same two positions in both orders.

    The cost is O(n²) pair checks. That is fine for small inputs, but the statement allows up to 100,000 elements, which would mean billions of pairs. The second lesson on this problem sorts the array first, after which only neighbouring elements need checking. Here the goal is to practise nested loops.

    Step by step

    1. Seed the best difference. Set minDiff to the absolute difference of the first two elements, and declare an empty minDiffPairs. Starting from a real difference avoids an artificial "no value yet" sentinel. It relies on the vector having at least two elements, which the constraints guarantee.
    2. Outer loop. The variable i picks the first element of the pair.
    3. Inner loop. The variable j starts at i + 1 and picks the second element.
    4. Measure the pair. curDiff is abs(nums[i] - nums[j]). The absolute value matters because nums[i] may be smaller or larger than nums[j].
    5. Check for a new record. If curDiff < minDiff, all earlier pairs are out of date.
    6. Replace the record. Set minDiff to curDiff and set minDiffPairs to a list holding only the new pair. The pair is written smaller value first with min and max, because nums[i] might be the larger one.
    7. Check for a tie. An else if catches curDiff == minDiff.
    8. Append the tied pair with push_back, again ordered with min and max.
    9. Sort and return. The pairs were found in input order, but the answer must be in ascending order, so sort minDiffPairs before returning it.

    The solution in C++

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

    The C++ details worth knowing:

    • The first pair is not lost. minDiffPairs starts empty even though minDiff already holds the first pair's difference. That works because the loops visit the pair of positions 0 and 1 as well, and it hits the tie branch (curDiff == minDiff) and is appended there.
    • Assigning a brace list. minDiffPairs = {{a, b}} replaces the whole contents of the vector with one inner vector. This discards the old pairs in a single statement.
    • push_back({a, b}). The braces build a vector<int> holding two numbers, which is then added as one new element.
    • Sorting vectors of vectors. The comparison of two vector<int> values is lexicographic: first elements decide, and the second elements break ties. That is exactly the "ascending with respect to pairs" order the problem asks for.
    • Signed and unsigned. nums.size() is unsigned, and the loop variables are int. The compiler may warn about the comparison. It is harmless here because the indices are never negative.
    • Reference parameter. vector<int>& nums avoids copying the vector. This solution doesn't change it.

    Complexity

    Time: O(n²). The two loops examine n * (n - 1) / 2 pairs, each in constant time. The final sort is on the result list, which has at most n - 1 pairs because the numbers are distinct, so it costs O(n log n) at most and doesn't change the total.

    Space: O(n) for the result. Besides the returned pairs, only a few integers are used.

    Edge cases and common mistakes

    • Exactly two elements. [5, 1] has a single pair, and the result is [[1, 5]]. Without min and max it would come out as [5, 1].
    • Several ties. [1, 2, 10, 11] has two pairs with difference 1, and the result is [[1, 2], [10, 11]].
    • Forgetting to clear the list on a new record. Pairs from an earlier, larger difference would stay in the result.
    • Using if twice instead of else if. After a new record, curDiff == minDiff is true, so the pair would be added a second time.
    • Forgetting the sort. The pairs come out in the order the loops find them, which follows the input. For [10, 11, 1, 2] the loops find [10, 11] first, so without the sort the result would be [[10, 11], [1, 2]] instead of [[1, 2], [10, 11]].
    • Starting j at 0. Elements would be paired with themselves, giving a difference of 0 and a wrong answer.

    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 C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free