# 2.24 Common Patterns

Array and string problems often look different on the surface, but many reduce to a small number of reusable patterns. The value of these patterns is that they provide a known invariant, a known complexity bound, and a known set of boundary cases. Once the pattern is recognized, the remaining work is mostly adapting the state and update rules.

## Pattern 1: Linear Scan

Use a linear scan when every element must be inspected once and the answer can be updated from a small amount of state.

```go
func CountPositive(a []int) int {
	count := 0

	for i := 0; i < len(a); i++ {
		if a[i] > 0 {
			count++
		}
	}

	return count
}
```

Invariant:

```text
Before iteration i, count equals the number of positive values in a[0:i].
```

Complexity:

```text
Time:  O(n)
Space: O(1)
```

## Pattern 2: Read and Write Pointers

Use read and write pointers when the result can be stored in the prefix of the same array.

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

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

	return a[:write]
}
```

Invariant:

```text
a[0:write] contains exactly the kept values from a[0:read], in order.
```

This pattern appears in filtering, stable compaction, deduplication, and in-place cleanup.

## Pattern 3: Two Pointers from Both Ends

Use opposite-end pointers when the input has symmetry or sorted order.

```go
func HasPairSumSorted(a []int, target int) bool {
	l := 0
	r := len(a) - 1

	for l < r {
		sum := a[l] + a[r]

		if sum == target {
			return true
		}
		if sum < target {
			l++
		} else {
			r--
		}
	}

	return false
}
```

Invariant:

```text
Any remaining valid pair must lie inside a[l:r+1].
```

The movement rule must be justified by sorted order.

## Pattern 4: Sliding Window

Use a sliding window when the answer depends on a contiguous range and the range can be updated by adding on the right and removing on the left.

```go
func LongestAtMostK(a []int, k int) int {
	l := 0
	sum := 0
	best := 0

	for r := 0; r < len(a); r++ {
		sum += a[r]

		for sum > k {
			sum -= a[l]
			l++
		}

		if r-l+1 > best {
			best = r - l + 1
		}
	}

	return best
}
```

Precondition:

```text
All values are nonnegative.
```

Invariant:

```text
After contraction, a[l:r+1] is a valid window.
```

## Pattern 5: Prefix Summary

Use prefix summaries when repeated range queries can be answered by subtracting two accumulated states.

```go
func PrefixSums(a []int) []int {
	p := make([]int, len(a)+1)

	for i := 0; i < len(a); i++ {
		p[i+1] = p[i] + a[i]
	}

	return p
}

func RangeSum(p []int, l, r int) int {
	return p[r] - p[l]
}
```

The range convention is half-open:

```text
[l, r)
```

Invariant:

```text
p[i] equals the sum of a[0:i].
```

## Pattern 6: Boundary Markers

Use boundary markers when many range updates are known before the final array is needed.

```go
func ApplyAdds(n int, updates [][3]int) []int {
	diff := make([]int, n+1)

	for _, u := range updates {
		l := u[0]
		r := u[1]
		x := u[2]

		diff[l] += x
		diff[r] -= x
	}

	out := make([]int, n)
	cur := 0

	for i := 0; i < n; i++ {
		cur += diff[i]
		out[i] = cur
	}

	return out
}
```

Each update uses a half-open range `[l, r)`.

Invariant:

```text
cur equals the total active update value at index i.
```

## Pattern 7: Frequency Table

Use a frequency table when multiplicity matters and order does not.

```go
func SameMultiset(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}

	count := make(map[int]int)

	for _, x := range a {
		count[x]++
	}

	for _, x := range b {
		count[x]--
		if count[x] < 0 {
			return false
		}
	}

	return true
}
```

Invariant:

```text
count[x] tracks how many more times x has appeared in a than in b so far.
```

## Pattern 8: Monotonic Stack

Use a monotonic stack when the nearest greater or nearest smaller element is needed.

```go
func NextGreater(a []int) []int {
	ans := make([]int, len(a))
	for i := range ans {
		ans[i] = -1
	}

	var st []int

	for i := 0; i < len(a); i++ {
		for len(st) > 0 && a[i] > a[st[len(st)-1]] {
			j := st[len(st)-1]
			st = st[:len(st)-1]
			ans[j] = a[i]
		}

		st = append(st, i)
	}

	return ans
}
```

Invariant:

```text
The stack contains indices whose next greater value has not yet been found, with values in decreasing order.
```

## Pattern 9: Hash-Based Lookup

Use a hash map when each element needs to query previously seen elements.

```go
func HasTwoSum(a []int, target int) bool {
	seen := make(map[int]struct{})

	for _, x := range a {
		if _, ok := seen[target-x]; ok {
			return true
		}
		seen[x] = struct{}{}
	}

	return false
}
```

Invariant:

```text
Before reading x, seen contains exactly the values before x.
```

## Pattern 10: Sort Then Scan

Use sorting when order can be changed and sorted structure simplifies the problem.

```go
func UniqueSortedCopy(a []int) []int {
	b := append([]int(nil), a...)
	sort.Ints(b)

	if len(b) == 0 {
		return b
	}

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

	return b[:write]
}
```

Requires:

```go
import "sort"
```

Complexity:

```text
Time:  O(n log n)
Space: O(n) for the copy
```

## Pattern Selection

| Problem shape                           | Likely pattern      |
| --------------------------------------- | ------------------- |
| Need one pass with small state          | Linear scan         |
| Need to remove or compact elements      | Read/write pointers |
| Sorted pair search                      | Two pointers        |
| Contiguous range with adjustable bounds | Sliding window      |
| Many range sum queries                  | Prefix sums         |
| Many offline range updates              | Difference array    |
| Need counts or multiplicity             | Frequency table     |
| Need nearest greater or smaller         | Monotonic stack     |
| Need lookup among previous values       | Hash map            |
| Order can be changed to simplify logic  | Sort then scan      |

## Common Pitfalls

Using a sliding window without monotonicity gives incorrect results.

Using read and write pointers without ensuring `write <= read` can overwrite unread values.

Using prefix sums with mixed interval conventions causes off-by-one errors.

Using maps for deterministic output without sorting keys gives unstable output order.

Sorting changes input order. Copy first if the original order matters.

Using an algorithmic pattern without stating its invariant makes edge cases harder to find.

## Takeaway

Most array and string algorithms are built from a small set of controlled scans. Identify the state, the update rule, and the invariant. Then choose the simplest pattern that preserves that invariant with the required complexity.