LESSON 255 OF 414 · TWO POINTERS

Array Diff in Scala: 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: |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 (not counting the sort itself and the returned pair).

STEP 1 OF 11

Guided

Ctrl + Enter to check

SCALA · TWO POINTERS

Array Diff in Scala, explained

Problem overview

The method arrayDiff(first: Array[Int], second: Array[Int]) receives two arrays of integers. It must return a pair [a, b], with a from first and b from second, such that the absolute difference |a - b| is as close to zero as possible.

For first = [4, 1, 8] and second = [12, 3, 17], the answer is [4, 3], because |4 - 3| = 1 and no other pair is closer.

The two arrays can have different lengths, and they can hold duplicates and negative numbers. The order inside the answer matters: the element from first comes first, and the element from second comes second.

The statement asks for O(n log n) time and O(1) extra space.

Approach: sort both, then sweep

Comparing every element of first with every element of second is correct but takes O(n * m). Sorting makes a linear sweep possible.

With both arrays ascending, put an index i at the front of first and an index j at the front of second. Compare the two current values and record the pair if its gap is the smallest so far. Then decide which index to move:

If first(i) is the smaller value, move i. The only way to shrink the gap is to raise the smaller side. Moving j would only pick a larger second(j) and widen the gap.
Otherwise second(j) is the smaller (or equal) value, so move j.

Each step moves one index forward, so the sweep takes at most n + m steps. Sorting costs O(n log n) and dominates.

Why can the skipped index be discarded safely? Suppose first(i) is smaller than second(j). Every later element of second is at least as large as second(j), so pairing it with first(i) gives a gap at least as big as the one just measured. Earlier elements of second have already been passed over by the sweep. So first(i) has no better partner, and the index can move on. The same argument works for second(j) when it is the smaller value.

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

1 vs 3   gap 2  best [1, 3]   1 is smaller, move i
4 vs 3   gap 1  best [4, 3]   3 is smaller, move j
4 vs 12  gap 8                4 is smaller, move i
8 vs 12  gap 4                8 is smaller, move i  (first is used up)

Step by step

Sort first in place with Sorting.quickSort(first). This sorts an Array[Int] directly, unlike first.sorted, which returns a new array.
Sort second the same way.
Declare i and j as vars starting at 0.
Declare smallestDiff as a var starting at Int.MaxValue, so that the first real gap replaces it.
Declare result as a var holding an empty array. It gets replaced each time a closer pair appears.
Loop while both indices are inside their arrays. Once either array is used up, no pair is left to examine.
Compute the gap as Math.abs(first(i) - second(j)).
If the gap is smaller than smallestDiff, store it and set result to Array(first(i), second(j)). The comparison is strict, so a later pair with the same gap doesn't replace the first one found.
Advance one index: i += 1 when first(i) is smaller, otherwise j += 1.
Return result.

The solution in Scala

class Solution {
    def arrayDiff(first: Array[Int], second: Array[Int]): Array[Int] = {
        Sorting.quickSort(first)
        Sorting.quickSort(second)
        var i = 0
        var j = 0
        var smallestDiff = Int.MaxValue
        var result = Array[Int]()
        while (i < first.length && j < second.length) {
            val diff = Math.abs(first(i) - second(j))
            if (diff < smallestDiff) {
                smallestDiff = diff
                result = Array(first(i), second(j))
            }
            if (first(i) < second(j)) {
                i += 1
            } else {
                j += 1
            }
        }
        return result
    }
}

The Scala details worth knowing:

The import. Sorting lives in the package scala.util. In a standalone file, the code needs import scala.util.Sorting at the top; without it, the compiler reports Not found: Sorting.
The inputs are changed. quickSort sorts the arrays in place. After the call, the caller's first and second are sorted. For the example, first becomes [1, 4, 8] and second becomes [3, 12, 17].
Array[Int]() creates an empty array. var allows result to be replaced with a new two-element array.
Math.abs comes from Java and works on Int. math.abs from Scala's own package gives the same result.
return at the end is allowed. The last expression, result alone, would do the same.

Complexity

Time: O(n log n). Sorting each array costs O(n log n) and O(m log m). The sweep is O(n + m), because every iteration moves one index and neither moves backward.

Space: O(1) extra. The sort works in place, and the sweep uses a few integers and a two-element result array.

Edge cases and common mistakes

An empty input. If either array is empty, the loop never runs and the method returns an empty array.
Equal values. [7] and [7] give [7, 7], a gap of 0, which is the best possible.
Several pairs with the same gap. The first one found wins. With [5, 5] and [5] the result is [5, 5].
Different lengths. The sweep ends when the shorter array is used up. The leftover elements of the longer one are never examined, which is safe because the pair that is closest to zero has already been seen.
Negative numbers. They need no special care: [-5, 2] and [-4, 30] give [-5, -4].
Moving the wrong pointer. Advancing the index at the larger value can skip the best pair.
Forgetting to sort one of the arrays. The sweep relies on both arrays being ascending.
Extreme values. Int subtraction wraps. For [Int.MinValue] and [Int.MaxValue], the difference first(i) - second(j) wraps around, and Math.abs reports a gap of 1 for a pair that is really 4294967295 apart. Computing the gap as a Long avoids this.

Testing

[4, 1, 8] and [12, 3, 17] give [4, 3].
[1, 10] and [4, 6] give [1, 4].
[-5, 2] and [-4, 30] give [-5, -4].
[7] and [7] give [7, 7].
[] and [1] give [].

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

Start learning free