# 2.4 Two Pointers

The two pointers technique uses two indices that move through an array or string in a controlled way. The main idea is to avoid restarting a scan from the beginning when useful information has already been discovered. When the pointers move monotonically, the total number of pointer movements is linear.

This pattern is useful when the problem has an ordered structure: sorted arrays, contiguous ranges, opposite-end searches, or windows whose boundaries only move forward.

## Problem

You need to inspect pairs, ranges, or partitions in an array without using a nested loop.

A direct pair search often looks like this:

```go
for i := 0; i < n; i++ {
	for j := i + 1; j < n; j++ {
		if good(a[i], a[j]) {
			return true
		}
	}
}
return false
```

This costs `O(n^2)`. Two pointers can reduce the cost to `O(n)` when the movement of one pointer gives information about how the other pointer should move.

## Solution

Maintain two indices. The exact meaning depends on the problem.

For a sorted array pair search, place one pointer at the left end and one pointer at the right end.

```go
func HasPairWithSum(a []int, target int) bool {
	left := 0
	right := len(a) - 1

	for left < right {
		sum := a[left] + a[right]

		if sum == target {
			return true
		}

		if sum < target {
			left++
		} else {
			right--
		}
	}

	return false
}
```

This assumes `a` is sorted in nondecreasing order.

## Why It Works

At each step, the algorithm considers the pair `(left, right)`.

If `a[left] + a[right] < target`, then pairing `a[left]` with any index at or below `right` cannot reach the target, because all those values are at most `a[right]`. Therefore `left` can be safely increased.

If `a[left] + a[right] > target`, then pairing `a[right]` with any index at or above `left` is too large, because all those values are at least `a[left]`. Therefore `right` can be safely decreased.

The sorted order gives the monotonic information that makes the discarded pairs safe.

## Invariant

During the loop, any valid answer that has not already been found must lie inside the current interval:

```text
left <= i < j <= right
```

When `left` is increased, all pairs using the old `left` are ruled out. When `right` is decreased, all pairs using the old `right` are ruled out.

The loop stops when `left >= right`, meaning no valid pair remains.

## Complexity

Each iteration moves either `left` or `right`. Neither pointer moves backward.

So the total number of pointer movements is at most `n`.

Time complexity:

```text
O(n)
```

Extra space:

```text
O(1)
```

## Opposite-End Pointers

The most common form starts from both ends.

Use it when the input is sorted or when the problem has symmetric structure.

Example: check whether a string is a palindrome.

```go
func IsPalindrome(s string) bool {
	left := 0
	right := len(s) - 1

	for left < right {
		if s[left] != s[right] {
			return false
		}
		left++
		right--
	}

	return true
}
```

Invariant:

All character pairs outside `[left, right]` have already been checked and are equal.

## Same-Direction Pointers

Sometimes both pointers move from left to right. This is common for compaction, filtering, and partitioning.

Example: remove all zero values while preserving order.

```go
func RemoveZeros(a []int) []int {
	write := 0

	for read := 0; read < len(a); read++ {
		if a[read] != 0 {
			a[write] = a[read]
			write++
		}
	}

	return a[:write]
}
```

Here `read` scans the input, and `write` marks the next output position.

Invariant:

Before each iteration, `a[0:write]` contains exactly the nonzero elements from `a[0:read]`, in the same order.

This is a two pointer algorithm even though only one pointer decides the loop condition.

## Partitioning

Partitioning places elements into groups according to a predicate.

Example: move all values less than `pivot` to the left.

```go
func PartitionLess(a []int, pivot int) int {
	write := 0

	for read := 0; read < len(a); read++ {
		if a[read] < pivot {
			a[write], a[read] = a[read], a[write]
			write++
		}
	}

	return write
}
```

After the function returns:

```text
a[0:write] contains values less than pivot
a[write:] contains values greater than or equal to pivot
```

This partition is not stable, because swapping may change the relative order of elements.

## Stable Partition by Writing

If order must be preserved, write accepted values forward.

```go
func StableFilterLess(a []int, pivot int) []int {
	write := 0

	for read := 0; read < len(a); read++ {
		if a[read] < pivot {
			a[write] = a[read]
			write++
		}
	}

	return a[:write]
}
```

This keeps the relative order of selected values, but it discards the rejected values from the returned slice.

## Three-Way Partition

A useful extension is three-way partitioning, often used for arrays with many duplicate values.

The goal is to rearrange the array into:

```text
values < pivot
values == pivot
values > pivot
```

```go
func ThreeWayPartition(a []int, pivot int) {
	lt := 0
	i := 0
	gt := len(a)

	for i < gt {
		if a[i] < pivot {
			a[lt], a[i] = a[i], a[lt]
			lt++
			i++
		} else if a[i] > pivot {
			gt--
			a[i], a[gt] = a[gt], a[i]
		} else {
			i++
		}
	}
}
```

Invariant:

```text
a[0:lt] contains values less than pivot
a[lt:i] contains values equal to pivot
a[i:gt] is unknown
a[gt:] contains values greater than pivot
```

When `a[i] > pivot`, the value swapped in from `gt - 1` has not yet been inspected, so `i` does not move.

## Removing Duplicates from a Sorted Array

Two pointers are also useful when duplicates are adjacent.

```go
func UniqueSorted(a []int) []int {
	if len(a) == 0 {
		return a
	}

	write := 1

	for read := 1; read < len(a); read++ {
		if a[read] != a[write-1] {
			a[write] = a[read]
			write++
		}
	}

	return a[:write]
}
```

Invariant:

Before each iteration, `a[0:write]` contains the unique values from `a[0:read]`.

Sorted order is essential. Without sorted order, equal values may be separated, and this local comparison would not remove all duplicates.

## Merging Two Sorted Arrays

Use one pointer per array.

```go
func MergeSorted(a, b []int) []int {
	out := make([]int, 0, len(a)+len(b))

	i := 0
	j := 0

	for i < len(a) && j < len(b) {
		if a[i] <= b[j] {
			out = append(out, a[i])
			i++
		} else {
			out = append(out, b[j])
			j++
		}
	}

	out = append(out, a[i:]...)
	out = append(out, b[j:]...)

	return out
}
```

Invariant:

Before each iteration, `out` contains the smallest `i + j` elements from the two inputs, in sorted order.

## Boundary Conditions

Two pointer code is short but sensitive to boundary errors.

For opposite-end pointers, use:

```go
for left < right {
	...
}
```

when the operation needs two distinct elements.

Use:

```go
for left <= right {
	...
}
```

when the middle element must also be processed.

For same-direction pointers, ensure that the write pointer never moves beyond the read pointer unless you intentionally write into separate storage.

For half-open intervals, prefer `[left, right)` when possible. It makes empty ranges natural and matches slice conventions.

## Common Pitfalls

The technique requires a reason why pointer movement is safe. Moving a pointer because it "seems smaller" or "seems larger" only works when the input order or invariant justifies it.

The pair-sum algorithm requires a sorted array. On an unsorted array, the same pointer movement discards candidates without proof.

In partitioning, advancing the scan pointer after every swap can skip unprocessed elements. In three-way partitioning, when a value is swapped from the right side into the current position, the current index must be inspected again.

In compaction algorithms, writing into the same array is safe only when `write <= read`. This ensures unread elements are not overwritten.

## Takeaway

Two pointers replace nested scanning with monotonic index movement. The method is correct when each pointer move safely discards a set of candidates. State that discard rule explicitly. Once the invariant is clear, the implementation is usually short, linear, and memory efficient.