12.2 Two Pointers | Algorithm Patterns | Infrastructure Development with Go

Two pointers work on sorted data or when you need to compare elements from different positions.

1 · Before you read — commit to an answer

nums := []int{1, 1, 2, 3, 3}
slow := 0
for fast := 1; fast < len(nums); fast++ {
    if nums[fast] != nums[slow] {
        slow++
        nums[slow] = nums[fast]
    }
}
fmt.Println(slow+1, nums)

3 [1 2 3 3 3]

Wrong is fine — the in-place section below walks through exactly this loop.

Merging Sorted Lists

Merging sorted log files — classic interview question:

// Merge two sorted slices of timestamps
func mergeSorted(a, b []int) []int {
    result := make([]int, 0, len(a)+len(b))
    i, j := 0, 0
    for i < len(a) && j < len(b) {
        if a[i] <= b[j] {
            result = append(result, a[i])
            i++
        } else {
            result = append(result, b[j])
            j++
        }
    }
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)
    return result
}

O(n+m) time, single pass through both lists.

Removing Duplicates In Place

2 · Worked example — read every step

// Remove duplicate consecutive entries from sorted slice
func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    slow := 0
    for fast := 1; fast < len(nums); fast++ {
        if nums[fast] != nums[slow] {
            slow++
            nums[slow] = nums[fast]
        }
    }
    return slow + 1 // new length
}

The slow pointer marks where to write. The fast pointer scans ahead. O(n) time, O(1) extra space. That's why the pretest slice still ends 3 3 3 — nothing past the new length is ever cleaned up.

Finding Pairs in Sorted Data

// Find two server capacities that sum to target (sorted input)
func twoSumSorted(capacities []int, target int) (int, int) {
    left, right := 0, len(capacities)-1
    for left < right {
        sum := capacities[left] + capacities[right]
        if sum == target {
            return left, right
        } else if sum < target {
            left++ // need a bigger number
        } else {
            right-- // need a smaller number
        }
    }
    return -1, -1
}

O(n) instead of O(n²). Only works on sorted data.

3 · Fill the gaps

Merge two sorted log streams into one — advance only the pointer you copied from, then drain whatever is left.

result := make([]int, 0, len(a)+len(b))
i, j := 0, 0
for i < len(a) &&  {
    if a[i] <= b[j] {
        result = append(result, a[i])
        
    } else {
        result = append(result, b[j])
        
    }
}
result = append(result, ...)
result = append(result, b[j:]...)
return result

The loop stops as soon as either stream runs dry; the two final appends drain the survivor (one of them is a no-op).

4 · From scratch — this feeds your review queue