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.

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

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

	return count
}

Invariant:

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

Complexity:

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.

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:

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.

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:

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.

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:

All values are nonnegative.

Invariant:

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.

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:

[l, r)

Invariant:

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.

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:

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.

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:

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.

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:

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.

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:

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.

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:

import "sort"

Complexity:

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.