Start learning free

LESSON 198 OF 348 · NESTED LOOPS & BRUTE FORCE

Minimum Absolute Difference in Kotlin: Brute Force Over All Pairs

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 10
    Ctrl + Enter to check

    KOTLIN · NESTED LOOPS & BRUTE FORCE

    Minimum Absolute Difference in Kotlin, explained

    Problem overview

    The function minimumAbsDifference(nums: IntArray): List<IntArray> receives an array of distinct integers. It looks at every two elements, finds the smallest absolute difference between any two of them, and returns every pair of elements that has exactly that difference. Each pair is written [a, b] with a < b, and the pairs come back in ascending order.

    For nums = [4, 2, 1, 3] the smallest difference is 1, and the pairs with that difference are [1, 2], [2, 3] and [3, 4]. For [1, 3, 6, 10, 15] the smallest difference is 2 and the only pair is [1, 3]. For [3, 8, -10, 23, 19, -4, -14, 27] the answer is [[-14, -10], [19, 23], [23, 27]], with a difference of 4 each.

    The array has at least two elements, so there is always at least one pair. The values are distinct, so no pair has a difference of 0.

    Approach: compare every pair and keep the best

    The brute-force idea is to compute the difference of every pair of elements and track two things: the smallest difference seen so far and the list of pairs that reach it. Each new pair is in one of three situations:

    • Its difference is smaller than the record. The old record is beaten, so every pair collected so far is wrong and the list restarts with this pair alone.
    • Its difference is equal to the record. It is another winner and joins the list.
    • Its difference is larger. Nothing happens.

    Looking at pairs (i, j) with j > i visits each unordered pair once. At the end, the list has the right pairs, but maybe in the wrong order, so the last step sorts them by their smaller element.

    To avoid a special "no value yet" state, the record starts as the difference of the first two elements. That pair is not put in the list yet. It is added later, when the loops reach it and find its difference equal to the record.

    Step by step

    1. Set up the record. Declare var minDiff = Math.abs(nums[0] - nums[1]) and var minDiffPairs = mutableListOf<IntArray>(). Both are var, because both are replaced during the search.
    2. Pick the first element with for (i in 0 until nums.size).
    3. Pick the second element with for (j in (i + 1) until nums.size), so every pair appears once and no element is paired with itself.
    4. Compute the difference. val curDiff = Math.abs(nums[i] - nums[j]) is a value that doesn't change, hence val.
    5. A new record. If curDiff < minDiff, set minDiff = curDiff and replace minDiffPairs by a new list holding only this pair. The pair is written smaller value first with intArrayOf(minOf(nums[i], nums[j]), maxOf(nums[i], nums[j])), because either of the two may be the smaller one.
    6. A tie. In an else if (curDiff == minDiff), add the same kind of pair to minDiffPairs.
    7. Sort. After the loops, minDiffPairs.sortBy { it[0] } sorts the list in place by the first element of each pair.
    8. Return minDiffPairs.

    On [4, 2, 1, 3] the record starts at 2, the difference of (4, 2). When the loops reach that pair it ties the record and is added as [2, 4]. The pair (4, 3) has difference 1, a new record, so the list restarts as [[3, 4]]. Then (2, 1) and (2, 3) tie and are added, and the list is [[3, 4], [1, 2], [2, 3]]. The sort puts it in order.

    The solution in Kotlin

    class Solution {
    fun minimumAbsDifference(nums: IntArray): List<IntArray> {
        var minDiff = Math.abs(nums[0] - nums[1])
        var minDiffPairs = mutableListOf<IntArray>()
        for (i in 0 until nums.size) {
            for (j in (i + 1) until nums.size) {
                val curDiff = Math.abs(nums[i] - nums[j])
                if (curDiff < minDiff) {
                    minDiff = curDiff
                    minDiffPairs = mutableListOf(intArrayOf(minOf(nums[i], nums[j]), maxOf(nums[i], nums[j])))
                } else if (curDiff == minDiff) {
                    minDiffPairs.add(intArrayOf(minOf(nums[i], nums[j]), maxOf(nums[i], nums[j])))
                }
            }
        }
        minDiffPairs.sortBy { it[0] }
        return minDiffPairs
    }
}

    The Kotlin details worth knowing:

    • The return type. The function returns a List<IntArray>: a list whose elements are arrays. The variable inside is a MutableList<IntArray>, which can be returned where a read-only List is expected.
    • Printing the result. A List<IntArray> prints each array as an object reference, such as [[I@.... To see the numbers, convert each pair, for example with joinToString and contentToString().
    • Math.abs. It comes from Java and works on Int. Kotlin's own kotlin.math.abs does the same. The difference of two values within the lesson's range of plus or minus a million fits easily in an Int. For extreme values, Int subtraction wraps silently.
    • minOf and maxOf. They return the smaller and the larger of two values, which puts the pair in a < b order.
    • sortBy { it[0] }. It sorts a mutable list in place by the key the lambda returns, here the first element of each pair. The sort is stable. Because the values are distinct, two tied pairs can never share their first element, so the result is fully ordered.
    • val and var. minDiffPairs is a var because the new-record branch assigns a fresh list to it.

    Complexity

    Time: O(n^2). The loops examine n(n - 1) / 2 pairs at constant cost each. The final sort costs O(k log k) for k tied pairs, and since k is less than n, it is small next to the loops. For an array near the statement's upper size of 100,000 elements, billions of pair checks is slow in practice. Sorting nums first would turn the search into a single pass, because the smallest differences are always between neighbours.

    Space: O(k) beyond the input, for the list of result pairs. In the worst case, such as consecutive integers, k is n - 1.

    Edge cases and common mistakes

    • Exactly two elements. [5, 1] returns [[1, 5]]. The record is that pair's own difference, and the loops add it as a tie.
    • Fewer than two elements. The code reads nums[1] at the start, so an array of one element throws an ArrayIndexOutOfBoundsException. The statement guarantees at least two elements.
    • Negative values. They work with no change: [-14, -10] has the difference 4.
    • Forgetting to reset the list. When a smaller difference appears, the old pairs must go. Only adding would leave pairs from larger differences in the answer.
    • Pairs in input order. Without minOf and maxOf, the pair from (4, 3) would appear as [4, 3] and break the a < b rule.
    • Skipping the sort. In the example, the loop produces [3, 4] first. The order only becomes ascending after sortBy.
    • Using <= in the first branch. A tie would reset the list instead of extending it, and only the last tied pair would survive.

    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]].
    • [10, 20, 30, 5] gives [[5, 10]].
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free