📖 Analogy
Two friends search a sorted bookshelf for two books whose page counts add to a target. One starts at the thin end, one at the thick end. Too few pages? The thin-end friend steps up to a fatter book. Too many? The thick-end friend steps down. They walk toward each other and meet in one pass — no need to compare every pair.
Converging pointers on sorted data
The brute-force way to find a pair summing to a target is two nested loops — O(n²). But if the slice is sorted, you can keep one index at each end and let the sum itself tell you which side to move:
- sum too small → move
loright (toward larger values), - sum too big → move
hileft (toward smaller values), - sum equal → found it.
Because the two indices only ever step toward each other, the loop runs at most n times — O(n) time, O(1) extra space.
graph LR A["[1, 3, 4, 6, 8, 11] target = 10"] --> B["lo=1 hi=11 → 12 too big, hi--"] B --> C["lo=1 hi=8 → 9 too small, lo++"] C --> D["lo=3 hi=8 → 11 too big, hi--"] D --> E["lo=3 hi=6 → 9 too small, lo++"] E --> F["lo=4 hi=6 → 10 found"]
package main
import "fmt"
// twoSumSorted returns the indices of two values that add up to target,
// or (-1, -1) if no such pair exists. The slice MUST be sorted ascending.
// Two pointers converge from the ends in a single O(n) pass.
func twoSumSorted(a []int, target int) (int, int) {
lo, hi := 0, len(a)-1
for lo < hi {
sum := a[lo] + a[hi]
switch {
case sum == target:
return lo, hi
case sum < target:
lo++ // need a bigger sum: move toward larger values
default:
hi-- // need a smaller sum: move toward smaller values
}
}
return -1, -1
}
func main() {
a := []int{1, 3, 4, 6, 8, 11}
target := 10
i, j := twoSumSorted(a, target)
if i == -1 {
fmt.Printf("no pair in %v sums to %d\n", a, target)
return
}
fmt.Printf("a[%d]=%d + a[%d]=%d = %d\n", i, a[i], j, a[j], target)
}
The sliding window
When the answer is some contiguous run — a subarray or a substring — you rarely need to restart from scratch at each position. Instead grow a window from the right and shrink it from the left, keeping a running summary as the edges move.
There are two flavours:
- Fixed window of size
k: slide it along, adding the entering element and subtracting the leaving one — the classic “max sum of anykconsecutive elements” in O(n). - Variable window: the right edge expands greedily; whenever the window breaks a rule, the left edge advances until the rule holds again.
The longest-substring-without-repeating-characters problem is the canonical variable window. Track the last-seen index of each byte; when the right edge meets a byte already inside the window, jump the left edge just past that earlier occurrence.
graph LR A["a b c a b c b b"] --> B["window grows: a, ab, abc"] B --> C["next a repeats → left jumps past old a"] C --> D["best length seen = 3 (abc)"]
package main
import "fmt"
// longestUnique returns the length of the longest substring of s
// that contains no repeated byte, using a variable-size sliding window.
// lastSeen[b] holds the most recent index at which byte b appeared.
func longestUnique(s string) int {
lastSeen := make(map[byte]int)
best, left := 0, 0
for right := 0; right < len(s); right++ {
b := s[right]
// If b is already inside the current window, shrink from the left
// to just past its previous position. The max guard stops the
// window from ever moving backward.
if prev, ok := lastSeen[b]; ok && prev >= left {
left = prev + 1
}
lastSeen[b] = right
if length := right - left + 1; length > best {
best = length
}
}
return best
}
func main() {
cases := []string{"abcabcbb", "bbbbb", "pwwkew", "golang"}
for _, s := range cases {
fmt.Printf("%-10s -> %d\n", s, longestUnique(s))
}
}
🐹 Sort first, then converge
Converging two pointers only work on sorted input — that’s what makes “move which side?” a valid decision. If your data isn’t sorted, you have a choice: pay O(n log n) to sort and then sweep in O(n), or keep it unsorted and use a hash table for an O(n)-time, O(n)-space pass. Sorting wins when you also need ordered output or the data is already nearly sorted.
⚠️ The left edge must never move backward
The bug that quietly breaks a variable window is letting the left pointer jump back. In the substring example, prev might point to a byte that left the window long ago; without the prev >= left guard, left would lurch backward, recount characters, and inflate the answer. Always clamp the left edge so it only ever moves forward — that’s also what guarantees the O(n) bound.
See also
- arrays & slices — the contiguous data two pointers sweep.
- sorting — the prerequisite for converging pointers.
- hash tables — the O(n)-space alternative when input isn’t sorted.
- binary search — the other “exploit sorted order” technique.
Next: when one pass isn’t enough — solving a problem in terms of itself with recursion and backtracking.
Related topics
A Go slice is a view over a backing array — how the (ptr, len, cap) header, append, growth, copy and re-slicing actually behave, and the aliasing traps.
algorithmsSortingWhy comparison sorts can't beat O(n log n) — merge sort and quicksort by hand, then the one line you actually write in Go: slices.Sort.
linearHash TablesAverage O(1) lookup via hashing — how Go's built-in map works, collisions and load factor, the comma-ok idiom, and the ordering and nil-map gotchas.
Check your understanding
Score: 0 / 51. On a sorted slice, two pointers find a pair summing to a target in what time?
lo and hi start at the ends and only ever move toward each other, so the loop runs at most n times. The slice must already be sorted for the move-which-pointer decision to be valid.
2. In the converging two-pointer pair-sum, when the current sum is too small you should:
Sorted ascending: the smallest unused increase comes from advancing lo. If the sum were too big you'd lower it by moving hi left instead.
3. What makes the sliding window for 'longest substring without repeating characters' O(n)?
Both edges only move right across the string, so each index is entered and left at most once — a total of O(n) edge moves, with O(1) map work per step.
4. What's the difference between a fixed-size and a variable-size sliding window?
A fixed window keeps width k constant — perfect for 'max sum of k consecutive elements,' updating in O(1) per slide. A variable window grows the right edge greedily and shrinks the left only when the window violates a rule (no repeats, sum ≤ target), still O(n) overall.
5. Besides pair-sum, which is a natural two-pointer problem?
Two pointers excel whenever a read index and a write/other index sweep an array: removing duplicates from a sorted slice (slow write pointer), merging two sorted inputs (one pointer each), reversing in place (ends converging), and three-way partitioning. The shared idea is one pass, O(1) extra space.
Comments
Sign in with GitHub to join the discussion.