LESSON 254 OF 414 · TWO POINTERS

Merge Sorted Arrays in Scala: O(n + m) with Two Indices

Practice O(n + m) Read the full explanation

Given two sorted arrays of integers, merge them into one sorted array containing all numbers

Example:

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

Output: [1, 1, 3, 4, 4, 8, 17]

Note:

Your algorithm should run in O(n + m) time and use O(n + m) extra space, where n and m are the lengths of the two arrays.

STEP 1 OF 10

Guided

Ctrl + Enter to check

SCALA · TWO POINTERS

Merge Sorted Arrays in Scala, explained

Problem overview

The method merge(first: Array[Int], second: Array[Int]) receives two arrays that are each sorted in ascending order. It returns one sorted array holding every number from both, duplicates included. For first = [1, 4, 8] and second = [1, 3, 4, 17] the result is [1, 1, 3, 4, 4, 8, 17].

The statement asks for O(n + m) time and O(n + m) extra space, where n and m are the two lengths. The extra space is simply the result array.

Approach: always take the smaller front element

Concatenating the arrays and sorting the result would work, but it costs O((n + m) log(n + m)) and ignores the fact that both inputs are already sorted. That fact gives a much cheaper method.

Since each array is sorted, its smallest unused element is at its front. The smallest element not yet in the result is therefore one of the two front elements. Compare them, move the smaller one into the result, and advance the index of the array it came from. Repeat. Each element is moved exactly once, so the work is linear.

When one array runs out, whatever remains of the other is already sorted and is all larger than or equal to everything copied so far, so it can be appended as it is.

In Scala that shortcut is (first ++ second).sorted, which is correct but does more work than this problem needs. The loop version also shows the pattern that sorted inputs allow: two indices that only ever move forward.

Take the example. The fronts are 1 (from first) and 1 (from second). They are equal, so the comparison 1 < 1 is false and the 1 from second goes in. The fronts are now 1 and 3, so the 1 from first goes in. Next come 3, then the 4 from second (the tie goes to second again), then the 4 from first, then 8. At that point first is used up, and the leftover 17 is appended without any comparison.

Step by step

Create a growable result. An Array has a fixed size, so use scala.collection.mutable.ArrayBuffer[Int](), which grows as elements are appended.
Declare two indices i and j as vars starting at 0, one per input array.
Loop while both arrays have elements: i < first.length && j < second.length. The loop stops as soon as either one is used up.
If first(i) < second(j), append first(i) and increment i.
Otherwise, append second(j) and increment j.
Drain first. A second loop appends every remaining element of first.
Drain second. A third loop does the same for second. After the main loop, at most one of the two drain loops has any work to do.
Convert and return. result.toArray turns the buffer into the Array[Int] the method must return. It is the last expression, so it is the method's value.

The solution in Scala

class Solution {
    def merge(first: Array[Int], second: Array[Int]): Array[Int] = {
        val result = scala.collection.mutable.ArrayBuffer[Int]()
        var i = 0
        var j = 0
        while (i < first.length && j < second.length) {
            if (first(i) < second(j)) {
                result += first(i)
                i += 1
            } else {
                result += second(j)
                j += 1
            }
        }
        while (i < first.length) {
            result += first(i)
            i += 1
        }
        while (j < second.length) {
            result += second(j)
            j += 1
        }
        result.toArray
    }
}

The Scala details worth knowing:

Array versus ArrayBuffer. An Array has a fixed length chosen when it is created. An ArrayBuffer can grow, and += appends one element to it. The buffer is a val because the name never changes; the buffer's contents do.
The full name. scala.collection.mutable.ArrayBuffer is written out in full here. An import scala.collection.mutable.ArrayBuffer would let you write just ArrayBuffer[Int]().
Indexing uses parentheses. It is first(i), not first[i].
No ++. Indices move with i += 1.
No return needed. The last expression of the method body, result.toArray, is its result.
toArray copies. The returned array is a new Array[Int], separate from the buffer, and neither input array is modified.

Complexity

Time: O(n + m). Every iteration of the three loops moves one element into the result and advances one index, and each index only moves forward. The loops run n + m times in total.

Space: O(n + m). The buffer ends with n + m elements, and toArray makes a second array of the same size. Both are linear.

Edge cases and common mistakes

An empty array. If first is empty, the main loop and the first drain loop do nothing, and the second drain loop copies all of second. If both are empty, the result is empty.
One array entirely smaller. [1, 2, 3] and [10, 11] give [1, 2, 3, 10, 11]: the main loop empties first, and the drain loop appends the rest of second.
Duplicates. Equal values go to the result one after the other. With integers, it doesn't matter which side a tie is taken from.
Skipping the drain loops. Without them, the leftover elements of the longer array are lost.
Forgetting to advance an index. The loop would append the same element forever.
Using || instead of && in the main loop. The loop would keep going after one array was used up and read past its end.

Testing

[1, 4, 8] and [1, 3, 4, 17] give [1, 1, 3, 4, 4, 8, 17].
[] and [2, 5] give [2, 5].
[2, 5] and [] give [2, 5].
[5] and [1, 2, 3] give [1, 2, 3, 5].
[] and [] 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