Two pointers

Picture two lines, each at its own service window. In each line people stand in ticket-number order, from smaller to larger. One window closes, and the two lines must become one, also in number order.

There is no need to rearrange everyone from scratch. It is enough to look at the first person in each line and let through the one with the smaller number. Each person goes through once, and the new line comes out in order right away.

In a program such lines are two sorted arrays. Joining them into one that is sorted too is called a merge. The shortest way is to join the arrays and sort the result with the sort method:

const a = [1, 3, 6, 8];
const b = [2, 3, 8];
const all = [...a, ...b].sort((x, y) => x - y);
console.log(all.join(" ")); // 1 2 3 3 6 8 8

Let's go through the line with sort:

1. [...a, ...b] spreads both arrays into one new array: [1, 3, 6, 8, 2, 3, 8].
2. sort((x, y) => x - y) puts it in ascending order.
3. all.join(" ") prints 1 2 3 3 6 8 8.

The result is correct, but sort is built for numbers in any order. The language does not promise that the method makes use of a and b being sorted already. Without that knowledge, sorting a long array makes noticeably more comparisons than there are numbers in it, while a merge needs at most one comparison per number.

Interviewers often ask to merge sorted arrays. The answer "join and sort" usually does not satisfy them: they expect a solution in one pass over both arrays.

Two indexes

The two pointers technique walks through data with two indexes, each of which moves on its own. A pointer here is an ordinary variable holding an element's position. In the lines, it is the finger you keep on the first person who has not gone through yet.

A merge step

In a merge, index i walks through a and index j walks through b. At each step:

1. a[i] and b[j] are compared.
2. The smaller of the two numbers goes into the result.
3. Only the index of that number moves.

On a tie either of the two can be taken, but here a[i] is taken. For the arrays from the example above, the steps are these:

The tail of an array

After the sixth step, array a has run out, and 8 is left in b. Such a tail is sorted already and no smaller than anything in the result. So it is appended whole to the result array out: out.push(...b.slice(j)).

Which array runs out first depends on the data. So after the loop both tails are appended, a.slice(i) and b.slice(j): the empty one adds nothing.

This is where the lines analogy ends. People leave a line, but the numbers in a and b stay where they are: only the indexes move, and the merge does not change the arrays themselves.

Each step sends one number to the result, so merging arrays of length n and m takes at most n + m steps.

Common elements

The same pass finds the numbers present in both sorted arrays:

const common = [];
let i = 0;
let j = 0;
while (i < a.length && j < b.length) {
    if (a[i] < b[j]) {
        i++;
    } else if (a[i] > b[j]) {
        j++;
    } else {
        common.push(a[i]);
        i++;
        j++;
    }
}
console.log(common.join(" ")); // 3 8

Let's see why the loop is built this way:

• The loop runs while both indexes are inside their arrays.
• The smaller number will not turn up later in the other array: only larger numbers stand there. So the index of the smaller number moves.
• Of two equal numbers, one goes into the result, and both indexes move.

Press "Next step" and watch i and j: at each step the index of the smaller number moves, and on a tie both do.

For these arrays the loop takes 5 steps, while comparing every number of a with every number of b would take 12.

Common mistake

The tail of an array is passed to push without the three dots:

const out = [1, 2, 3];
const rest = [7, 9];
out.push(rest); // ✗
console.log(out.length);

There is no error, but the program prints 4, not 5. The push method got one argument, an array, and put it into out whole, as one element. Spread syntax splits the tail into separate numbers: out.push(...rest).

Key points

• Two sorted arrays are merged in one pass with two indexes, without sort.
• At each step the smaller number goes into the result, and only its index moves.
• After the loop both tails are appended: a.slice(i) and b.slice(j).
• An array is passed to push with three dots, or it lands in the result as one element.