Start learning free

LESSON 206 OF 348 · SORTING

Minimum Absolute Difference in Kotlin: Sort and Compare Neighbours

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

    KOTLIN · SORTING

    Minimum Absolute Difference in Kotlin, explained

    Problem overview

    minimumAbsDifference takes an IntArray of distinct integers and finds the smallest difference between any two of its elements. It returns every pair [a, b] with a < b and b - a equal to that smallest difference, as a List<IntArray> in ascending order.

    For [4, 2, 1, 3] the smallest difference is 1, and the pairs 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].

    Approach

    Comparing every pair of elements is correct, but it takes O(n^2) time, which is too slow for 100,000 elements.

    Sorting makes the problem local. If two elements x < z have a third element y between them in sorted order, then y - x and z - y are both smaller than z - x. So a pair with something between it can never be the closest pair, and the minimum difference always occurs between neighbours. Only n - 1 neighbouring pairs need checking.

    The sort also solves the output order. Pairs taken from left to right in a sorted array are already in ascending order, and each has a < b because the values are distinct.

    The scan keeps the smallest gap seen so far and the list of pairs with that gap. A smaller gap replaces the list; an equal gap adds to it.

    Step by step

    1. Sort nums in place with sort().
    2. Set the starting minimum. Declare var minDiff as nums[1] - nums[0], the gap of the first pair, which is a real gap in the array. Also declare val minDiffPairs as an empty mutableListOf<IntArray>(). It is a val because the list object stays the same while its contents change.
    3. Loop over neighbouring pairs with for (i in 1 until nums.size). Each i stands for the pair nums[i - 1], nums[i].
    4. Compute the gap: val curDiff = nums[i] - nums[i - 1]. Because the array is sorted, it is never negative.
    5. If curDiff < minDiff, a new record has been found. Set minDiff to curDiff, clear() the list, because all earlier pairs have a larger gap, and add the new pair as intArrayOf(nums[i - 1], nums[i]).
    6. Otherwise, if curDiff == minDiff, add the pair to the list without clearing.
    7. Return minDiffPairs.

    Note that on the first iteration curDiff equals the starting minDiff, so the first pair is added by the else if branch.

    The solution in Kotlin

    class Solution {
    fun minimumAbsDifference(nums: IntArray): List<IntArray> {
        nums.sort()
        var minDiff = nums[1] - nums[0]
        val minDiffPairs = mutableListOf<IntArray>()
        for (i in 1 until nums.size) {
            val curDiff = nums[i] - nums[i - 1]
            if (curDiff < minDiff) {
                minDiff = curDiff
                minDiffPairs.clear()
                minDiffPairs.add(intArrayOf(nums[i - 1], nums[i]))
            } else if (curDiff == minDiff) {
                minDiffPairs.add(intArrayOf(nums[i - 1], nums[i]))
            }
        }
        return minDiffPairs
    }
}

    Kotlin details worth knowing:

    • The return type is List<IntArray>, a read-only view. Inside the function the object is a MutableList, which is why clear() and add() are allowed there; returning it as a List is fine.
    • Each pair is a fresh IntArray made with intArrayOf. Printing an IntArray directly shows a reference-style text, so use toList() or joinToString() to display it.
    • if / else if is a statement here, with no value used.
    • The subtraction can't overflow for the lesson's range of -1,000,000 to 1,000,000, since differences stay within 2,000,000. With values near Int.MIN_VALUE and Int.MAX_VALUE the difference could wrap around, and you would use Long.

    Tracing [3, 8, -10, 23, 19, -4, -14, 27]: after sorting it is [-14, -10, -4, 3, 8, 19, 23, 27], and the gaps between neighbours are 4, 6, 7, 5, 11, 4 and 4. The starting minimum is 4, and the first pair [-14, -10] is added. The gap 6 and the following gaps 7, 5 and 11 change nothing. The gaps 4 at [19, 23] and [23, 27] equal the minimum, so both are appended.

    The check for a smaller gap comes first and the equal check second. If both used <= in one branch, you would need to clear the list only for strictly smaller gaps, which is exactly why the lesson splits the cases.

    Complexity

    • Time: O(n log n) for the sort and O(n) for the scan.
    • Space: O(1) extra for the sort and variables, not counting the returned list. In the worst case, such as [1, 2, 3, 4], it holds n - 1 pairs.

    Edge cases and common mistakes

    • Two elements. There is one pair, and it is returned.
    • Not clearing the list. Without clear() on a new minimum, pairs with a larger gap would stay in the result.
    • Checking only the first minimum. Several pairs can share the minimum gap, as in [-14, -10], [19, 23] and [23, 27], so keep going after finding one.
    • Skipping the sort. Then neighbours in the input are not neighbours in value, and the pairs would not be in ascending order either.
    • Starting minDiff at 0. Distinct values never have a gap of 0, so nothing would ever be smaller or equal, and the result would stay empty.
    • Declaring minDiff with val. It is reassigned when a smaller gap appears, so Kotlin reports an error unless it is a var. The list, by contrast, is never reassigned, so val is correct for it.
    • Reusing one pair array. Add a new intArrayOf(...) each time. Adding the same array and changing it later would change every stored pair.

    Testing

    • [4, 2, 1, 3] returns [[1, 2], [2, 3], [3, 4]].
    • [1, 3, 6, 10, 15] returns [[1, 3]].
    • [3, 8, -10, 23, 19, -4, -14, 27] returns [[-14, -10], [19, 23], [23, 27]].
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free