Two Pointers

This module moves into one of the most common patterns in both interviews and the Forge Algorithm Lab: shaping a solution using two index pointers walking across an existing array or string, rather than building an entirely new data structure. It is the same spirit as binary search's left and right pointers, generalized beyond just searching.

Given a sorted array, find two numbers that add up to a target value. The brute-force approach checks every pair directly with nested loops - O(n²), the same shape flagged back in the "measuring code" module. Because the array is sorted, a smarter approach places one pointer at the very start (the smallest value) and one at the very end (the largest value): if the pair's sum is too big, the right pointer must move inward, since increasing the smaller side could never help; if the sum is too small, the left pointer moves inward instead. Every step discards at least one possibility permanently, so the two pointers together cover the entire array in a single O(n) pass.

Tracing it on items = [1, 3, 4, 6, 9, 11], target = 13: left = 0 (value 1), right = 5 (value 11), sum = 12, too small, so left advances. left = 1 (value 3), right = 5 (value 11), sum = 14, too big, so right retreats. left = 1 (value 3), right = 4 (value 9), sum = 12, too small, so left advances. left = 2 (value 4), right = 4 (value 9), sum = 13, a match - returning indices (2, 4).

A second classic shape uses two pointers starting at opposite ends and converging toward the middle, swapping as they go, rather than one pointer racing ahead of the other.

This runs in O(n) time, touching each element once, and notably O(1) extra space - no new list is allocated, matching the space-complexity lens introduced back in the "measuring code" module. Building a reversed copy with items[::-1] is simpler to write, but it costs O(n) extra space; the two-pointer swap version above is the in-place alternative.