LESSON 231 OF 348 · TWO POINTERS

Merge Sorted Arrays in Kotlin: O(n + m) with Two Pointers

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.

STEP 1 OF 10

Guided

Ctrl + Enter to check

KOTLIN · TWO POINTERS

Merge Sorted Arrays in Kotlin, explained

Problem overview

The function merge receives two IntArrays, first and second, each already sorted in ascending order. It returns one new IntArray with all the numbers from both, also sorted. Duplicates stay: every element of both inputs appears in the result.

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 sizes.

Approach: always take the smaller front element

The simplest idea is to put everything into one array and sort it. That costs O((n + m) log(n + m)) and ignores the fact that the inputs are already ordered. The faster idea uses that order.

The smallest number not yet merged is always at the front of one of the two arrays, because each array is sorted. So keep one index per array. Compare the two front elements, move the smaller one to the result, and advance that array's index. Each comparison places exactly one element, so the whole merge takes n + m steps.

At some point one array runs out. The other one may still have elements, and they are all at least as large as everything placed so far and already in order, so they can be copied over without any more comparing.

Walking through the example, the fronts are 1 and 1. They are equal, so the one from second goes first (the comparison is a strict <), then 1 from first, then 3, then the two 4s, and 8. By then first is used up, and the remaining 17 from second is copied at the end.

Step by step

Make the result list. An ArrayList<Int> grows as elements are added, which suits a result whose size is the sum of two inputs. It's a val because only its contents change.
Create two indices. i points into first and j into second. They are vars starting at 0.
Loop while both arrays have elements. The condition is i < first.size && j < second.size, so neither array is read out of bounds.
If first[i] is smaller, add it to the result and increment i.
Otherwise add second[j] and increment j. This branch also handles equal values.
Drain first. A loop on i < first.size copies whatever is left of it.
Add the rest of first one element at a time, moving i forward.
Drain second. A loop on j < second.size does the same for the other array. Only one of the two drain loops has anything to do, since the main loop stopped when one array was used up.
Add the rest of second and move j forward.
Convert and return. The function returns an IntArray, so call toIntArray() on the list.

The solution in Kotlin

class Solution {
    fun merge(first: IntArray, second: IntArray): IntArray {
        val result = ArrayList<Int>()
        var i = 0
        var j = 0
        while (i < first.size && j < second.size) {
            if (first[i] < second[j]) {
                result.add(first[i])
                i++
            } else {
                result.add(second[j])
                j++
            }
        }
        while (i < first.size) {
            result.add(first[i])
            i++
        }
        while (j < second.size) {
            result.add(second[j])
            j++
        }
        return result.toIntArray()
    }
}

Kotlin details worth knowing:

IntArray versus ArrayList<Int>. An IntArray has a fixed size and stores plain ints. An ArrayList<Int> can grow, but it stores boxed Integer objects. The solution builds in the list because it adds elements one by one, then converts once at the end. toIntArray() copies the list into a new IntArray.
val on a list. val result means the name can't be pointed at another list. result.add(...) still works, because it changes the list, not the variable.
size is a property. Write first.size without parentheses, unlike a method call.
Allocating the result directly. Since the final size is known to be first.size + second.size, an IntArray(first.size + second.size) with a write index would avoid the list and the conversion. The lesson's version is simpler to read.

Complexity

Time: O(n + m). Each loop iteration adds one element to the result and advances an index, and no index ever moves backward. In total the three loops run n + m iterations. The final toIntArray() is another O(n + m) pass.

Space: O(n + m). The result list holds every element, and the converted array holds them again. Both are proportional to n + m.

Edge cases and common mistakes

One or both arrays empty. With first = [] and second = [2, 5] the main loop never runs and the second drain loop copies everything, giving [2, 5]. Two empty arrays give an empty array.
All of one array before the other. [1, 2] and [3, 4] finish the main loop after consuming first; the drain loop appends [3, 4]. The result is [1, 2, 3, 4].
Forgetting a drain loop. Without it, the leftover elements, like the 17 in the example, are silently dropped.
Forgetting to advance an index. The loop would then add the same element forever.
Duplicates. Equal values from both arrays all appear in the result, so this isn't a set union.
Returning the list. The return type is IntArray, so a List<Int> won't compile there.

Testing

first = [1, 4, 8], second = [1, 3, 4, 17] gives [1, 1, 3, 4, 4, 8, 17].
first = [], second = [2, 5] gives [2, 5].
first = [1, 2], second = [3, 4] gives [1, 2, 3, 4].
first = [], second = [] 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