LESSON 255 OF 415 · TWO POINTERS

Merge Sorted Arrays in Swift: 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, where n and m are the lengths of the two arrays.

STEP 1 OF 10

Guided

Ctrl + Enter to check

SWIFT · TWO POINTERS

Merge Sorted Arrays in Swift, explained

Problem overview

The method merge receives two arrays of integers, first and second, each already sorted in ascending order. It returns one sorted array that contains every number from both.

For first = [1, 4, 8] and second = [1, 3, 4, 17] the answer is [1, 1, 3, 4, 4, 8, 17]. Numbers that appear in both arrays appear twice in the result, because every element is kept.

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

Approach: always take the smaller front element

The simplest idea is to join the arrays and sort the result. It works, but it costs O((n + m) log(n + m)) and ignores the fact that the inputs are sorted already.

Use the order instead. In a sorted array the smallest element not yet used is the one at the front. So the smallest unused element overall must be one of two candidates: the front of first or the front of second. Compare those two, move the smaller into the result, and advance in the array it came from. Repeat until one array runs out, then copy what is left of the other one, which is already sorted and no smaller than anything in the result.

On the example, the indices start at 0. The fronts are 1 and 1, and the tie goes to second, so the result starts with 1 and j moves on. Then 1 against 3 takes the 1 from first. Then 4 against 3 takes the 3, 4 against 4 takes the 4 from second, 4 against 17 takes the 4 from first, and 8 against 17 takes the 8. Now first is used up, and the loop that copies the rest of second appends 17.

Why this is correct

At every moment, the result holds the smallest i + j elements of the two arrays, in order. The next element to add must be the smallest of the rest. Everything left in first is at least first[i] and everything left in second is at least second[j], so the smaller of those two fronts can't be beaten. Adding it keeps the property true. When one array runs out, whatever remains of the other is already in order and no smaller than anything in the result, so it can be appended unchanged.

Why not do it in place

The statement allows O(n + m) extra space, so the code builds a fresh array. Merging inside one of the inputs is possible, but it needs more care about overwriting elements that haven't been read yet, and it isn't what this lesson asks for.

Step by step

Create result as an empty [Int] with var, since the code appends to it.
Declare two indices, i for first and j for second, both starting at 0.
Loop while both arrays have elements left: i < first.count and j < second.count.
If first[i] is smaller, append it and advance i.
Otherwise, append second[j] and advance j. Ties take this branch, which is harmless for plain integers.
Drain first. A second loop appends whatever remains in first.
Drain second. A third loop does the same for second. At most one of these two loops runs.
Return result.

The solution in Swift

class Solution {
    func merge(_ first: [Int], _ second: [Int]) -> [Int] {
        var result = [Int]()
        var i = 0, j = 0
        while i < first.count && j < second.count {
            if first[i] < second[j] {
                result.append(first[i])
                i += 1
            } else {
                result.append(second[j])
                j += 1
            }
        }
        while i < first.count {
            result.append(first[i])
            i += 1
        }
        while j < second.count {
            result.append(second[j])
            j += 1
        }
        return result
    }
}

Swift details worth knowing:

Declaring two variables at once. var i = 0, j = 0 declares both on one line, and both are Int.
Empty array. [Int]() creates an empty array of integers. var result: [Int] = [] means the same.
Parameters are constants. The method only reads first and second, so it needs no copies. It builds a new array and leaves the inputs unchanged.
No ++. Swift has no increment operator, so the indices advance with += 1.
count. It is a property, so it is written without parentheses.

Complexity

Time: O(n + m). Every iteration of every loop appends one element and advances one index, and the indices never move back. The three loops together run n + m times.

Space: O(n + m). The result holds every element of both arrays. Nothing else grows with the input.

Edge cases and common mistakes

An empty array. The first loop never starts, and one of the draining loops copies the other array. merge([], [2, 3]) returns [2, 3].
Both empty. The result is [].
One array entirely smaller. merge([1, 2, 3], [7, 8]) empties first in the main loop, then the drain loop copies 7 and 8.
Forgetting the drain loops. The main loop stops when either array is used up, so without them the leftover elements are lost.
Duplicates and negatives. merge([-5, 0], [-5, -1]) returns [-5, -5, -1, 0]. Both copies of -5 are kept.
Sorting at the end. It gives the right answer but breaks the time bound.
Advancing the wrong index. Moving i when you appended from second repeats or skips elements.

Testing

[1, 4, 8] and [1, 3, 4, 17] give [1, 1, 3, 4, 4, 8, 17].
[] and [2, 3] give [2, 3].
[1, 2, 3] and [7, 8] give [1, 2, 3, 7, 8].
[-5, 0] and [-5, -1] give [-5, -5, -1, 0].

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

Start learning free