LESSON 232 OF 348 · TWO POINTERS

Array Diff in Kotlin: O(n log n) with Sorting and Two Pointers

Practice O(n log n) Read the full explanation

Given two arrays of integers, find a pair of integers, one from each array, whose absolute difference is the closest to zero.

Example:

Input: first =[4, 1, 8],
       second = [12, 3, 17]

Output: [4, 3]
Explanation: abs(4-3) = 1 which is the closest to 0

Note:

Your algorithm should run in O(n log n) time and use O(1) extra space.

STEP 1 OF 11

Guided

Ctrl + Enter to check

KOTLIN · TWO POINTERS

Array Diff in Kotlin, explained

Problem overview

The function arrayDiff receives two IntArrays, first and second. It must find one number from each array so that the absolute difference between them is as close to zero as possible, and return those two numbers as an IntArray, the one from first before the one from second.

For first = [4, 1, 8] and second = [12, 3, 17] the closest pair is 4 and 3, because abs(4 - 3) = 1 and no other pair is closer. The answer is [4, 3]. The statement asks for O(n log n) time and O(1) extra space.

Approach: sort both arrays, then sweep

Trying every pair costs O(n * m) comparisons. Sorting removes most of that work.

Once both arrays are in ascending order, keep one pointer in each: i in first and j in second. Look at the pair they point to and record its difference if it beats the best so far. Then decide which pointer to move. If first[i] is the smaller of the two, the only way to bring the values closer is to raise it, so advance i. Advancing j would pick an even larger second value, and the gap could only grow. In the other case, advance j.

Every move discards a value that can't form a closer pair with anything still ahead, so the sweep is linear. The sorting is O(n log n), which makes it the dominant cost.

On the example, the sorted arrays are [1, 4, 8] and [3, 12, 17]:

1 and 3 differ by 2, so the best is [1, 3]. 1 is smaller, so i moves.
4 and 3 differ by 1, a new best: [4, 3]. Now 3 is smaller, so j moves.
4 and 12 differ by 8, and 8 and 12 differ by 4. Neither beats 1, and first runs out.

The result is [4, 3].

Step by step

Sort first in place with sort(). The pointer sweep depends on ascending order.
Sort second the same way.
Create the pointers. i and j are vars starting at 0, one per array.
Create smallestDiff, starting at Int.MAX_VALUE so that the first real difference is always smaller.
Create result, a var holding an empty IntArray from intArrayOf(). It is replaced whenever a closer pair turns up.
Loop while both pointers are inside their arrays. When either array is used up, no more pairs can be formed.
Compute diff as the absolute value of first[i] - second[j].
Record a better pair. If diff < smallestDiff, update both smallestDiff and result.
Move the pointer at the smaller value: if first[i] < second[j], increment i.
Otherwise increment j. This covers the case where second[j] is smaller and the case where the two values are equal.
Return result.

The solution in Kotlin

class Solution {
    fun arrayDiff(first: IntArray, second: IntArray): IntArray {
        first.sort()
        second.sort()
        var i = 0
        var j = 0
        var smallestDiff = Int.MAX_VALUE
        var result = intArrayOf()
        while (i < first.size && j < second.size) {
            val diff = Math.abs(first[i] - second[j])
            if (diff < smallestDiff) {
                smallestDiff = diff
                result = intArrayOf(first[i], second[j])
            }
            if (first[i] < second[j]) {
                i++
            } else {
                j++
            }
        }
        return result
    }
}

Kotlin details worth knowing:

sort() changes the caller's arrays. On an IntArray, sort() reorders the array itself and returns nothing. After the call, the arrays passed in are sorted: with the example, first becomes [1, 4, 8] and second becomes [3, 12, 17]. sorted() would return a new List<Int> and leave the array alone. Sorting in place is what keeps the extra space small.
Math.abs. This is the Java library function, which Kotlin code can call directly. The Kotlin form is kotlin.math.abs, which needs an import; both work on Int.
intArrayOf() with no arguments makes an empty IntArray. The variable's type is inferred as IntArray, so it can later be assigned a two-element array.
Int.MAX_VALUE is 2147483647, the largest Int.
Overflow in the subtraction. Int is 32 bits and wraps silently. A difference such as 2000000000 - (-2000000000) doesn't fit and wraps to a negative number, whose absolute value is wrong. Values in the lesson's tests are small enough that this doesn't arise. A Long subtraction would be safe for any Int inputs.

Complexity

Let n and m be the two sizes.

Time: O(n log n + m log m), which is O(n log n) for inputs of similar size. The sweep takes at most n + m steps, since each iteration moves one pointer forward and no pointer moves back.

Space: O(1) beyond the inputs. The function keeps a few integers and one two-element result. The sort works in place on the arrays, which is why they end up modified.

Edge cases and common mistakes

An empty array. The loop never runs and the function returns an empty array.
Ties. The comparison is a strict <, so a later pair with the same difference does not replace an earlier one. For [1, 5] and [3], both pairs differ by 2, and the answer is [1, 3].
Equal values. [1] and [1] give [1, 1], a difference of 0.
Forgetting to sort. The rule for moving pointers is only valid on ascending arrays.
Moving the wrong pointer. Advancing the pointer at the larger value can only increase the gap, so the sweep could skip the best pair.
Result order. The pair is always (value from first, value from second), even when the second is smaller: [5, 2] and [7, 3] give [2, 3].

Testing

first = [4, 1, 8], second = [12, 3, 17] gives [4, 3].
first = [1, 5], second = [3] gives [1, 3].
first = [5, 2], second = [7, 3] gives [2, 3].
first = [1], second = [1] gives [1, 1].
first = [], second = [3] gives [].

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

Start learning free