LESSON 194 OF 344 · NESTED LOOPS & BRUTE FORCE

Minimum Absolute Difference in Java: Brute Force with Nested Loops

Practice O(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 <= 10⁵
-10⁶ <= nums[i] <= 10⁶

STEP 1 OF 9

Guided

Ctrl + Enter to check

JAVA · NESTED LOOPS & BRUTE FORCE

Minimum Absolute Difference in Java, explained

Problem overview

The method minimumAbsDifference receives an array nums of distinct integers. 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 by its first element.

Take nums = [4, 2, 1, 3]. The pairs (1, 2), (2, 3) and (3, 4) differ by 1, and no pair differs by less, because the values are distinct. The answer is [[1, 2], [2, 3], [3, 4]]. For [1, 3, 6, 10, 15] the smallest difference is 2, found only in (1, 3), so the answer is [[1, 3]].

Approach: check every pair, keep the best so far

The direct idea is to look at every pair of positions (i, j) with i < j. For each pair, compute the absolute difference and compare it to the best one seen so far. This lesson belongs to the nested-loops chapter, so it uses exactly that.

The comparison has three outcomes:

The new difference is smaller than the best. It is a new record, so every pair collected before is wrong. Throw the old list away and start a new one with this pair.
The difference equals the best. This pair ties, so add it to the list.
The difference is larger. Ignore the pair.

With n elements there are about n * (n - 1) / 2 pairs, so the running time is O(n²). A faster idea exists: once the array is sorted, the closest pairs must be neighbours, so only adjacent elements need checking. That version is covered in the sorting chapter. Here the point is to practise nested loops and the "reset on a new record" pattern.

Step by step

Start the best difference at the first pair. Set minDiff to Math.abs(nums[0] - nums[1]). That is a real difference from the input, so no special "nothing yet" value is needed. Create minDiffPairs, an empty List<List<Integer>>.
Loop over the first element. The outer loop variable i runs over every index.
Loop over the second element. The inner variable j starts at i + 1. Starting there means each pair is visited once, and an element is never paired with itself.
Compute the difference as curDiff, using Math.abs since either value can be larger.
Test for a new record with curDiff < minDiff.
On a record, reset. Update minDiff, replace the list with a fresh empty one and add the new pair. The pair is built as [smaller, larger] with Math.min and Math.max, because nums[i] may be the larger value.
Test for a tie with an else if on curDiff == minDiff.
On a tie, append the pair in the same [smaller, larger] form.
Sort and return. Pairs were found in index order, not value order. Sorting the list by each pair's first element produces the required ascending order.

The solution in Java

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] nums) {
        int minDiff = Math.abs(nums[0] - nums[1]);
        List<List<Integer>> minDiffPairs = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int curDiff = Math.abs(nums[i] - nums[j]);
                if (curDiff < minDiff) {
                    minDiff = curDiff;
                    minDiffPairs = new ArrayList<>();
                    minDiffPairs.add(Arrays.asList(Math.min(nums[i], nums[j]), Math.max(nums[i], nums[j])));
                } else if (curDiff == minDiff) {
                    minDiffPairs.add(Arrays.asList(Math.min(nums[i], nums[j]), Math.max(nums[i], nums[j])));
                }
            }
        }
        minDiffPairs.sort((a, b) -> a.get(0) - b.get(0));
        return minDiffPairs;
    }
}

The Java details worth a closer look:

The first pair is handled by the loop. minDiff starts equal to the difference of nums[0] and nums[1], but minDiffPairs starts empty. When the loops reach i = 0, j = 1, the difference equals minDiff, so the tie branch adds that pair. Nothing is lost.
Arrays.asList and boxing. Arrays.asList(a, b) with two int values boxes them to Integer and gives a List<Integer>, which matches the element type of minDiffPairs. The list has a fixed size: you can read it and replace elements, but not add or remove.
Replacing the list. Assigning new ArrayList<>() to minDiffPairs drops the old pairs. Calling clear() would work too. The diamond <> lets Java infer the element type from the variable.
The comparator. (a, b) -> a.get(0) - b.get(0) is a lambda for Comparator. It returns a negative number when a comes first. get(0) returns an Integer, which unboxes for the subtraction. The subtraction is safe here because the values are at most 1,000,000 in size; for arbitrary int values it could overflow, and Integer.compare(a.get(0), b.get(0)) would be the safer form.
List.sort. It sorts the list in place. Since the numbers are distinct, no two pairs share the same first element, so ties in the sort cannot occur.

Complexity

Time: O(n²) for the loops. The inner body runs once per pair, about n²/2 times. Sorting the k collected pairs adds O(k log k), which is small next to the loops since k is below n. For the largest sizes in the statement (n up to 100,000) this approach would be far too slow, which is the reason the sorted version exists.

Space: O(k) for the result, plus a few integers. Each reset discards the previous list for the garbage collector to reclaim.

Edge cases and common mistakes

Two elements. [5, 2] returns [[2, 5]]. The pair is reordered with Math.min and Math.max.
Appending without resetting. If a new record only adds its pair, the older pairs with larger differences stay in the list.
Only handling <. Without the else if for ties, the result keeps just one pair per difference, so Example 1 would return a single pair.
Starting j at i. The difference of an element with itself is 0, which would win every time.
Forgetting to order each pair. Writing Arrays.asList(nums[i], nums[j]) gives [4, 2] when 4 comes earlier in the array.
Skipping the final sort. On [4, 2, 1, 3] the loops find [3, 4] first (the record), then [1, 2] and [2, 3] as ties. That order is not ascending, and the sort puts it right.

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, 2] gives [[2, 5]].
[1, 4, 7, 10] gives [[1, 4], [4, 7], [7, 10]].

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

Start learning free