LESSON 231 OF 348 · TWO POINTERS

Merge Sorted Arrays in TypeScript: 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

TYPESCRIPT · TWO POINTERS

Merge Sorted Arrays in TypeScript, explained

Problem overview

The method merge receives two arrays of numbers, first and second, each already sorted in ascending order. It returns one new sorted array that contains every number from both. Duplicates are kept: no value is dropped or merged.

In the example, first = [1, 4, 8] and second = [1, 3, 4, 17]. The result is [1, 1, 3, 4, 4, 8, 17]: both 1s and both 4s appear.

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

Approach: always take the smaller front element

The simplest idea is to concatenate the arrays and sort the result. That costs O((n + m) log(n + m)) and ignores the fact that the inputs are already sorted. Because they are, the smallest number not yet placed must be at the front of one of the two arrays. So there are only two candidates to compare at any moment.

Keep one index in each array. Compare the two current elements, copy the smaller one to the result, and move that array's index forward. Each comparison places exactly one number, so the whole merge takes n + m steps.

At some point one array runs out. The other one may still have numbers left, and they are all at least as large as everything already placed, so they can be copied over as they are.

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

Compare 1 and 1: not smaller, so the 1 from second goes in. Result: [1].
Compare 1 and 3: the 1 from first goes in. Result: [1, 1].
Compare 4 and 3: 3 goes in. Then 4 against 4: the 4 from second goes in. Then 4 against 17: the 4 from first goes in. Result: [1, 1, 3, 4, 4].
Compare 8 and 17: 8 goes in, and first is used up. Result: [1, 1, 3, 4, 4, 8].
Copy the rest of second: 17.

Step by step

Create result as an empty number[]. The annotation matters: with no elements to look at, TypeScript can't work out the element type of an empty array literal by itself.
Declare i and j, both 0. They point at the next unused element of first and second.
Loop while both indices are in range. The loop stops as soon as one array is used up.
If first[i] < second[j], push first[i] and advance i.
Otherwise, push second[j] and advance j. This branch also handles equal values.
Drain first. A second loop, while i < first.length, copies what is left of it.
Drain second. A third loop does the same for j. At most one of these two loops runs, because the main loop ended when one array was exhausted.
Return result.

The solution in TypeScript

class Solution {
    merge(first: number[], second: number[]): number[] {
        let result: number[] = [];
        let i = 0, j = 0;
        while (i < first.length && j < second.length) {
            if (first[i] < second[j]) {
                result.push(first[i]);
                i++;
            } else {
                result.push(second[j]);
                j++;
            }
        }
        while (i < first.length) {
            result.push(first[i]);
            i++;
        }
        while (j < second.length) {
            result.push(second[j]);
            j++;
        }
        return result;
    }
}

The TypeScript details worth a closer look:

number[] is the type of an array of numbers. With let result: number[] = [], the compiler knows push accepts numbers and that the return type matches.
Indices are plain numbers. let i = 0, j = 0; declares two variables in one statement, and TypeScript infers number for both.
push modifies the array in place and appends at the end, which is a constant-time operation on average.
The inputs are never changed. Only reads and a new result array are involved, so the caller's arrays are exactly as they were.
Reading past the end gives undefined, not an error. That is why the bounds checks on i and j come first. A comparison with undefined is always false, so a missing check would quietly corrupt the result instead of failing.

Complexity

Time: O(n + m). Every loop iteration pushes one number and advances one index. Each index only moves forward, so the three loops together run at most n + m times.

Space: O(n + m). The result array holds all n + m numbers. The two indices use constant space.

Edge cases and common mistakes

An empty array. If first is empty, the main loop never runs, and the second drain loop copies all of second. Merging two empty arrays returns [].
One array entirely smaller. [1, 2, 3] and [7, 8] produce [1, 2, 3, 7, 8]: the main loop empties first and a drain loop copies the rest of second.
Forgetting the drain loops. Without them, the numbers left over in the longer array are lost.
Concatenating and calling sort() with no comparator. The default sort compares elements as strings, so [5, 10, 1, 2] becomes [1, 10, 2, 5]. A comparator such as (a, b) => a - b fixes the order, but the result is still slower than the merge.
Dropping duplicates. Equal values from the two arrays must both appear. The else branch takes one of them now and the other on a later iteration.
Forgetting to advance an index. If i++ or j++ is missing, the loop pushes the same number forever.

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 = [] gives [1, 2].
first = [5, 6], second = [1, 2] gives [1, 2, 5, 6].
first = [], second = [] gives [].

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

Start learning free