# 2.25 Boundary Conditions

Boundary conditions define the valid domain of indices, ranges, and states in an algorithm. Many bugs arise not from the main logic, but from incorrect handling of edges such as empty input, single-element cases, or off-by-one errors. This section provides a systematic approach to designing and verifying boundaries.

## Problem

Given an algorithm over arrays or strings, ensure correctness for all valid inputs, including edge cases:

```text id="h7q3zp"
empty input
single element
full range
minimal and maximal indices
```

## Index Ranges

Two common conventions:

```text id="m1d8uk"
inclusive: [l, r]
half-open: [l, r)
```

Half-open ranges are usually safer because:

```text id="k9s0qx"
length = r - l
empty range: l == r
```

Example:

```go id="x3p1sz"
for i := l; i < r; i++ {
	// process a[i]
}
```

Invariant:

```text id="c5t9vy"
At iteration i, elements in a[l:i] have already been processed
```

## Off-by-One Errors

Typical mistake:

```go id="j6u2na"
for i := 0; i <= len(a); i++ { // wrong
```

Correct:

```go id="w8y4lx"
for i := 0; i < len(a); i++ {
```

Reason:

```text id="p0k7rf"
valid indices: 0 to len(a)-1
```

## Empty Input

Always check before accessing elements.

```go id="r4n9hs"
if len(a) == 0 {
	return
}
```

Accessing `a[0]` without this check causes a panic.

## Single Element

Some algorithms assume at least two elements.

Example:

```go id="t2k8vd"
if len(a) == 1 {
	return a[0]
}
```

Two-pointer algorithms must handle:

```text id="s1j6zw"
l == r
```

depending on whether a single element is valid.

## Two Pointers Boundaries

Opposite-end pattern:

```go id="c3v8lm"
for l < r {
	...
}
```

Same-direction pattern:

```go id="h5q2zn"
for r < n {
	...
}
```

Invariant:

```text id="f6x1op"
l and r always remain within [0, n]
```

Mistake:

```text id="y9e3ck"
using l <= r when logic requires two distinct elements
```

## Sliding Window Boundaries

Window `[l, r]` or `[l, r)` must be consistent.

Example with inclusive:

```go id="m8r1dw"
for r := 0; r < n; r++ {
	for invalid {
		l++
	}
}
```

Invariant:

```text id="k4n2ye"
window contains elements from l to r inclusive
```

Common error:

```text id="v3h7ta"
mixing r-l and r-l+1 inconsistently
```

## Matrix Boundaries

Check both dimensions:

```go id="u2d6xs"
if 0 <= r && r < rows && 0 <= c && c < cols {
```

Mistake:

```text id="q1m5lf"
using rows for both dimensions
```

## Prefix Arrays

Prefix array size is `n + 1`.

```go id="g9y3bn"
p := make([]int, n+1)
```

Access pattern:

```text id="z8c2qp"
p[0] = 0
p[i] = sum of first i elements
```

Range query:

```go id="k7w1tr"
sum := p[r] - p[l]
```

Mistake:

```text id="e6v9sn"
using p[r-1] or mixing inclusive/exclusive conventions
```

## Difference Arrays

For half-open updates `[l, r)`:

```go id="f3b8px"
d[l] += x
d[r] -= x
```

For inclusive `[l, r]`:

```go id="j2c4yt"
d[l] += x
d[r+1] -= x
```

Mistake:

```text id="p8z6mq"
accessing d[r+1] when r is already the last index without extra space
```

## Binary Search Boundaries

Two standard forms:

### Lower Bound

```go id="n7d3lw"
l, r := 0, n
for l < r {
	m := (l + r) / 2
	if a[m] < target {
		l = m + 1
	} else {
		r = m
	}
}
```

Invariant:

```text id="c1z9qt"
[l, r) always contains the answer
```

### Upper Bound

```go id="w5r8vd"
l, r := 0, n
for l < r {
	m := (l + r) / 2
	if a[m] <= target {
		l = m + 1
	} else {
		r = m
	}
}
```

Mistake:

```text id="h4y2sk"
using inconsistent updates leads to infinite loops
```

## Loop Termination

Ensure progress in every iteration.

Bad:

```go id="b6k3nr"
for l < r {
	if condition {
		l++
	}
}
```

If `condition` is false, loop does not progress.

Correct:

```go id="q1v8mz"
for l < r {
	if condition {
		l++
	} else {
		r--
	}
}
```

## Sentinel Values

Sentinels simplify boundary logic.

Example:

```go id="t8z1pn"
a := append(a, math.MaxInt)
```

Now comparisons do not need to check end conditions inside loops.

Use carefully to avoid modifying original data unintentionally.

## Edge Case Checklist

Before finalizing an algorithm, test:

```text id="u6m9ra"
n = 0
n = 1
all elements equal
strictly increasing
strictly decreasing
maximal input size
minimal input size
```

## Common Pitfalls

Mixing inclusive and half-open ranges in the same function.

Forgetting to handle empty input before indexing.

Using incorrect loop bounds.

Failing to update pointers in all branches.

Incorrect matrix dimension checks.

Assuming sorted input when it is not guaranteed.

## Design Pattern

Boundary handling follows:

1. Choose a consistent range convention
2. State valid index domain
3. Maintain invariant within that domain
4. Ensure loop progress
5. Verify termination condition

## Takeaway

Correct boundary handling is as important as the main algorithm. Most runtime errors and subtle bugs come from incorrect index limits and inconsistent range definitions. Use half-open intervals when possible, state invariants explicitly, and test extreme cases early.