Go Guide

Core patterns · Lesson 17 of 62 · about 45 min

Two pointers

Replace a nested loop with two indexes that move toward each other or in the same direction, using what you know about the data to skip work.

Go by Example: Slices ↗pkg.go.dev: slices.Compact ↗
On this page · 11 sections
  1. 01Shape 1: opposite ends
  2. 02Shape 2: same direction (fast and slow)
  3. 03Shape 3: fix one, two-pointer the rest (3Sum)
  4. 04Two Sum, every variation
  5. 05Trapping rain water
  6. 06The full program
  7. 07Complexity
  8. 08Recognizing the pattern
  9. 09Summary
  10. 10Check your understanding
  11. 11Practice in Go

Shape 1: opposite ends#

Start l at the beginning and r at the end of a sorted slice, and move them toward each other.

"Find two numbers that add up to target." Look at nums[l] + nums[r]:

  • Equal to target: done.
  • Too small: the only way to grow the sum is a bigger left value, so l++. (Pairing nums[l] with anything left of r would be even smaller, so nums[l] is useless.)
  • Too big: r-- by the same argument.

Trace nums = [1, 3, 4, 6, 8, 11], target = 10:

lrnums[l] + nums[r]action
051 + 11 = 12too big: r--
041 + 8 = 9too small: l++
143 + 8 = 11too big: r--
133 + 6 = 9too small: l++
234 + 6 = 10found (2, 3)

Each step moves one pointer inward, so there are at most n steps.

Palindromes use the same shape without sorting: compare s[l] and s[r], then move both inward.

Run the trace

The same search, printing one line per step. Try a target that does not exist, such as 2, and watch the pointers cross:

pairsum_trace.go
Go
package main
 
import "fmt"
 
func main() {
	nums, target := []int{1, 3, 4, 6, 8, 11}, 10
	l, r := 0, len(nums)-1
	for l < r {
		s := nums[l] + nums[r]
		fmt.Printf("l=%d r=%d  %d + %-2d = %-2d ", l, r, nums[l], nums[r], s)
		switch {
		case s == target:
			fmt.Printf("found (%d, %d)\n", l, r)
			return
		case s < target:
			fmt.Println("too small: l++")
			l++
		default:
			fmt.Println("too big: r--")
			r--
		}
	}
	fmt.Println("no pair")
}
Output
l=0 r=5  1 + 11 = 12 too big: r--
l=0 r=4  1 + 8  = 9  too small: l++
l=1 r=4  3 + 8  = 11 too big: r--
l=1 r=3  3 + 6  = 9  too small: l++
l=2 r=3  4 + 6  = 10 found (2, 3)

A palindrome check is the same loop with a different comparison:

palindrome.go
Go
package main
 
import "fmt"
 
func isPalindrome(s string) bool {
	for l, r := 0, len(s)-1; l < r; l, r = l+1, r-1 {
		fmt.Printf("  compare s[%d]=%c with s[%d]=%c\n", l, s[l], r, s[r])
		if s[l] != s[r] {
			return false
		}
	}
	return true
}
 
func main() {
	for _, w := range []string{"racecar", "gopher"} {
		fmt.Println(w)
		fmt.Println("  palindrome:", isPalindrome(w))
	}
}
Output
racecar
  compare s[0]=r with s[6]=r
  compare s[1]=a with s[5]=a
  compare s[2]=c with s[4]=c
  palindrome: true
gopher
  compare s[0]=g with s[5]=r
  palindrome: false

Step through it

Shape 2: same direction (fast and slow)#

Both pointers start at the left. fast reads every element; slow marks where the next kept element should be written. This compacts a slice in place with O(1) extra memory.

"Remove duplicates from a sorted slice, in place." Trace [1, 1, 2, 3, 3]:

fastnums[fast]same as previous?writeslow afterslice prefix
1[1]
11yes1[1]
22nonums[1] = 22[1 2]
33nonums[2] = 33[1 2 3]
43yes3[1 2 3]

Return slow = 3: the first 3 elements are the answer.

Run the trace

Watch slow stay put on duplicates while fast keeps reading. After the loop, only the first slow elements matter; whatever is left after them is leftover data, not part of the answer:

dedup_trace.go
Go
package main
 
import "fmt"
 
func main() {
	nums := []int{1, 1, 2, 3, 3}
	slow := 1
	for fast := 1; fast < len(nums); fast++ {
		if nums[fast] == nums[fast-1] {
			fmt.Printf("fast=%d nums[fast]=%d duplicate, skip      slow=%d %v\n", fast, nums[fast], slow, nums[:slow])
			continue
		}
		nums[slow] = nums[fast]
		slow++
		fmt.Printf("fast=%d nums[fast]=%d new: write nums[%d]  slow=%d %v\n", fast, nums[fast], slow-1, slow, nums[:slow])
	}
	fmt.Println("answer:", nums[:slow], " whole slice:", nums)
}
Output
fast=1 nums[fast]=1 duplicate, skip      slow=1 [1]
fast=2 nums[fast]=2 new: write nums[1]  slow=2 [1 2]
fast=3 nums[fast]=3 new: write nums[2]  slow=3 [1 2 3]
fast=4 nums[fast]=3 duplicate, skip      slow=3 [1 2 3]
answer: [1 2 3]  whole slice: [1 2 3 3 3]

Shape 3: fix one, two-pointer the rest (3Sum)#

"Find all unique triplets summing to 0." Sort, then for each i, find pairs in nums[i+1:] that sum to -nums[i] with opposite-end pointers. O(n) per i gives O(n²) total, far better than O(n³). Skip equal neighbors to avoid duplicate triplets.

Run the trace

This prints every i that 3Sum fixes and every triplet it finds. Note how i=2 is skipped because it starts with the same number as i=1:

threesum_trace.go
Go
package main
 
import (
	"fmt"
	"slices"
)
 
func main() {
	nums := []int{-1, 0, 1, 2, -1, -4}
	slices.Sort(nums)
	fmt.Println("sorted:", nums)
	for i := 0; i < len(nums)-2; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			fmt.Printf("i=%d nums[i]=%d same as before, skip\n", i, nums[i])
			continue
		}
		fmt.Printf("i=%d nums[i]=%d look for pairs summing to %d in %v\n", i, nums[i], -nums[i], nums[i+1:])
		l, r := i+1, len(nums)-1
		for l < r {
			s := nums[i] + nums[l] + nums[r]
			switch {
			case s < 0:
				l++
			case s > 0:
				r--
			default:
				fmt.Println("    found", []int{nums[i], nums[l], nums[r]})
				l++
				r--
				for l < r && nums[l] == nums[l-1] {
					l++
				}
			}
		}
	}
}
Output
sorted: [-4 -1 -1 0 1 2]
i=0 nums[i]=-4 look for pairs summing to 4 in [-1 -1 0 1 2]
i=1 nums[i]=-1 look for pairs summing to 1 in [-1 0 1 2]
    found [-1 -1 2]
    found [-1 0 1]
i=2 nums[i]=-1 same as before, skip
i=3 nums[i]=0 look for pairs summing to 0 in [1 2]

Two Sum, every variation#

"Two Sum" is not one problem but a family. The right tool depends on what the input guarantees and what the question returns:

VariationBest approachTimeSpace
unsorted, return indexeshash map of value → index (hashing lesson)O(n)O(n)
sorted, return a pairopposite-end pointersO(n)O(1)
count pairs with sum < targetsort, then pointers: if a[l]+a[r] < t, all of l+1..r pair with lO(n log n)O(1)
all unique pairssort, pointers, skip equal neighborsO(n log n)O(1)
3Sum, 4Sum, k-Sumsort, fix one element, recurse down to 2SumO(n^(k-1))O(k) recursion
a data stream (add, then query)a count map; check target - x for each distinct xO(1) add, O(n) queryO(n)

The general k-Sum reduces to the sorted Two Sum: fix the first number, solve (k-1)-Sum on the rest with the remaining target, skipping duplicates at every level.

ksum.go
Go
package main
 
import (
	"fmt"
	"slices"
)
 
func twoSumHash(nums []int, target int) (int, int) {
	seen := map[int]int{}
	for i, n := range nums {
		if j, ok := seen[target-n]; ok {
			return j, i
		}
		seen[n] = i
	}
	return -1, -1
}
 
// countLess counts pairs i < j with a[i] + a[j] < target (a must be sorted).
func countLess(a []int, target int) int {
	count := 0
	for l, r := 0, len(a)-1; l < r; {
		if a[l]+a[r] < target {
			count += r - l // a[l] pairs with every index in l+1..r
			l++
		} else {
			r--
		}
	}
	return count
}
 
// kSum returns every unique k-tuple from sorted a that sums to target.
func kSum(a []int, k, target int) [][]int {
	var res [][]int
	if k == 2 {
		for l, r := 0, len(a)-1; l < r; {
			switch s := a[l] + a[r]; {
			case s < target:
				l++
			case s > target:
				r--
			default:
				res = append(res, []int{a[l], a[r]})
				for l++; l < r && a[l] == a[l-1]; l++ {
				}
				r--
			}
		}
		return res
	}
	for i := 0; i < len(a)-k+1; i++ {
		if i > 0 && a[i] == a[i-1] {
			continue // same first number: same tuples as before
		}
		for _, rest := range kSum(a[i+1:], k-1, target-a[i]) {
			res = append(res, append([]int{a[i]}, rest...))
		}
	}
	return res
}
 
func main() {
	fmt.Println(twoSumHash([]int{3, 2, 4}, 6))
	fmt.Println("pairs with sum < 2:", countLess([]int{-1, 1, 2, 3}, 2)) // (-1,1) and (-1,2)
	a := []int{1, 0, -1, 0, -2, 2}
	slices.Sort(a)
	fmt.Println("4Sum = 0:", kSum(a, 4, 0))
	fmt.Println("3Sum = 0:", kSum([]int{-4, -1, -1, 0, 1, 2}, 3, 0))
}
Output
1 2
pairs with sum < 2: 2
4Sum = 0: [[-2 -1 1 2] [-2 0 0 2] [-1 0 0 1]]
3Sum = 0: [[-1 -1 2] [-1 0 1]]

Trapping rain water#

Given bar heights, how much rain water is trapped between them? The water above bar i is min(tallest bar to its left, tallest bar to its right) - height[i], if positive.

Precomputing both maxima takes two extra arrays. Two pointers do it in O(1) extra space: keep leftMax and rightMax, and always move the pointer on the lower side. If height[l] < height[r], there is a wall at least as tall as height[l] on the right, so the water at l depends only on leftMax, which is known. The mirror argument handles the right side.

rainwater.go
Go
package main
 
import "fmt"
 
func trap(h []int) int {
	l, r := 0, len(h)-1
	leftMax, rightMax, water := 0, 0, 0
	for l < r {
		if h[l] < h[r] {
			leftMax = max(leftMax, h[l])
			water += leftMax - h[l]
			l++
		} else {
			rightMax = max(rightMax, h[r])
			water += rightMax - h[r]
			r--
		}
	}
	return water
}
 
func main() {
	fmt.Println(trap([]int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}))
	fmt.Println(trap([]int{4, 2, 0, 3, 2, 5}))
	fmt.Println(trap([]int{1, 2, 3, 4})) // rising: nothing is trapped
}
Output
6
9
0

The stacks lesson solves the same problem a second way, filling water layer by layer with a monotonic stack.

The full program#

twopointers.go
Go
package main
 
import (
	"fmt"
	"slices"
)
 
func twoSumSorted(nums []int, target int) (int, int) {
	l, r := 0, len(nums)-1
	for l < r {
		switch s := nums[l] + nums[r]; {
		case s == target:
			return l, r
		case s < target:
			l++
		default:
			r--
		}
	}
	return -1, -1
}
 
func isPalindrome(s string) bool {
	isAlnum := func(c byte) bool {
		return 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' || '0' <= c && c <= '9'
	}
	lower := func(c byte) byte {
		if 'A' <= c && c <= 'Z' {
			return c + 'a' - 'A'
		}
		return c
	}
	l, r := 0, len(s)-1
	for l < r {
		for l < r && !isAlnum(s[l]) {
			l++
		}
		for l < r && !isAlnum(s[r]) {
			r--
		}
		if lower(s[l]) != lower(s[r]) {
			return false
		}
		l++
		r--
	}
	return true
}
 
func removeDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	slow := 1
	for fast := 1; fast < len(nums); fast++ {
		if nums[fast] != nums[fast-1] {
			nums[slow] = nums[fast]
			slow++
		}
	}
	return slow
}
 
func threeSum(nums []int) [][]int {
	nums = slices.Clone(nums)
	slices.Sort(nums)
	var res [][]int
	for i := 0; i < len(nums)-2; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue // same first number as before
		}
		l, r := i+1, len(nums)-1
		for l < r {
			s := nums[i] + nums[l] + nums[r]
			switch {
			case s < 0:
				l++
			case s > 0:
				r--
			default:
				res = append(res, []int{nums[i], nums[l], nums[r]})
				l++
				r--
				for l < r && nums[l] == nums[l-1] {
					l++ // skip duplicate second numbers
				}
			}
		}
	}
	return res
}
 
func maxArea(h []int) int {
	best, l, r := 0, 0, len(h)-1
	for l < r {
		best = max(best, min(h[l], h[r])*(r-l))
		if h[l] < h[r] {
			l++
		} else {
			r--
		}
	}
	return best
}
 
func main() {
	fmt.Println(twoSumSorted([]int{1, 3, 4, 6, 8, 11}, 10))
	fmt.Println(isPalindrome("A man, a plan, a canal: Panama"), isPalindrome("race a car"))
	nums := []int{1, 1, 2, 3, 3}
	k := removeDuplicates(nums)
	fmt.Println(k, nums[:k])
	fmt.Println(threeSum([]int{-1, 0, 1, 2, -1, -4}))
	fmt.Println(maxArea([]int{1, 8, 6, 2, 5, 4, 8, 3, 7}))
}
Output
2 3
true false
3 [1 2 3]
[[-1 -1 2] [-1 0 1]]
49

Complexity#

ProblemTimeExtra space
pair sum in sorted sliceO(n)O(1)
palindrome checkO(n)O(1)
remove duplicates in placeO(n)O(1)
3SumO(n²)O(1) besides output (sorting a copy costs O(n))
container with most waterO(n)O(1)

Recognizing the pattern#

  • Input is sorted, or sorting it does not lose information you need.
  • The question is about pairs or triplets with a target sum or difference.
  • You must modify a slice in place with O(1) extra memory.
  • Something is symmetric (palindromes, reversing).

Summary#

  • Opposite ends on sorted data: move the pointer that can improve the answer.
  • Fast/slow in the same direction: fast reads, slow writes; in-place, O(1) space.
  • Fix one element and two-pointer the rest to handle triplets in O(n²).
  • Always be able to say why a move never skips a valid answer.

Check your understanding

Answer before scrolling back up. If you miss one, reread the matching section, then try again.

  1. Q1.Opposite-end pointers find a pair with a given sum in O(n) only if the slice is:

  2. Q2.In the sorted pair search, the sum is too small. Which pointer moves?

  3. Q3.In the fast/slow 'remove duplicates' pattern, what does slow mark?

  4. Q4.In Container With Most Water, why move the shorter line inward?

Practice in Go

Write a table test first, then the solution. On LeetCode, choose Go as the language. Open a hint only after 15 minutes stuck.

Finished this lesson?

Mark it done to track your progress. It is saved in this browser only.