Two pointers

Picture two guest lists, each in alphabetical order, that need to become one. Nobody would shuffle all the guests together and sort them again. It works better to put a finger on the start of each list. Each time you copy out the name that comes first alphabetically and move that finger one line down.

In Go, the same task is merging two sorted slices into one that is also sorted. You can gather all the numbers into one slice and sort it with the slices.Sort function:

package main

import (
    "fmt"
    "slices"
)

func main() {
    a := []int{1, 4, 6}
    b := []int{2, 3, 7}
    all := append([]int{}, a...)
    all = append(all, b...)
    slices.Sort(all)
    fmt.Println(all) // [1 2 3 4 6 7]
}

Let's walk through it line by line:

1. all := append([]int{}, a...) copies the numbers of a into a new slice.
2. all = append(all, b...) appends the numbers of b to them.
3. slices.Sort(all) sorts all six numbers, and the program prints [1 2 3 4 6 7].

The result is correct, but the sort ignores that both halves are already in order and rearranges every number. A merge does the job in one pass over both slices—like two fingers moving down two lists.

Two indices

The two pointers technique walks through data with two indices, each of which moves on its own.

A pointer here is an ordinary int variable holding an element's position, not a Go pointer with * and &. A finger rests on a line of the list; it does not hold that line's address.

Merging

In a merge, each index is in charge of its own slice:

• the index i walks through a;
• the index j walks through b;
• at each step, the smaller of a[i] and b[j] (either one, if they are equal) goes into the result, and only its index moves.

For the slices from the example above, the steps are these:

Press "Next step" to walk through the same merge in a program: watch i and j in the main frame, since only one of them moves per step.

Each step sends one number into the result, so merging slices of lengths n and m takes at most n + m steps.

Tails after the loop

After the fifth step, the slice a has run out, and 7 remains in b. Here is what happens to such a remainder:

1. The tail is already sorted and larger than everything in the result.
2. So it is appended whole: append(out, b[j:]...).
3. Which slice runs out first depends on the data, so after the loop both tails are appended, a[i:] and b[j:]: the empty one adds nothing.

Where the technique appears

This technique comes up often in interviews:

• the merge is the main step of merge sort;
• two pointers solve many tasks on sorted data.

Common elements

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

a, b := []int{1, 3, 4, 8}, []int{2, 3, 8, 9}
var common []int
i, j := 0, 0
for i < len(a) && j < len(b) {
    if a[i] < b[j] {
        i++
    } else if a[i] > b[j] {
        j++
    } else {
        common = append(common, a[i])
        i++
        j++
    }
}
fmt.Println(common) // [3 8]

The loop runs while both indices are inside their slices. The smaller number cannot appear further on in the other slice: only larger numbers stand there. So each step has three possible cases:

• a[i] < b[j]—i moves;
• a[i] > b[j]—j moves;
• the numbers are equal—the number goes into common, and both indices move.

Let's trace the first steps:

1. 1 < 2 moves i.
2. 3 > 2 moves j.
3. 3 and 3 are equal and go into common.

For these slices, the loop takes five steps, while comparing every number with every other would take sixteen.

Common mistake

The loop condition is written with || to reach the end of both slices:

a := []int{1, 2}
b := []int{5}
i, j := 0, 0
for i < len(a) || j < len(b) { // ✗
    if a[i] < b[j] {
        i++
    } else {
        j++
    }
}

panic: runtime error: index out of range [2] with length 2

Here is what happens:

1. Once a runs out, the loop keeps going for b.
2. The loop reads a[2] past the end of the slice: the finger has slid off the list.
3. The program stops with a panic.

Keep && in the condition, and handle the rest of the other slice after the loop. In a merge, it is appended with append.

Key points

• Two pointers are two int indices that walk through the data and move independently.
• Merging two sorted slices: the smaller of a[i] and b[j] goes into the result, and both tails are appended after the loop.
• A merge takes at most n + m steps instead of sorting every number again.
• The loop condition is &&: with ||, an index runs past the end of a slice, and the program panics.