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:

empty input
single element
full range
minimal and maximal indices

Index Ranges

Two common conventions:

inclusive: [l, r]
half-open: [l, r)

Half-open ranges are usually safer because:

length = r - l
empty range: l == r

Example:

for i := l; i < r; i++ {
	// process a[i]
}

Invariant:

At iteration i, elements in a[l:i] have already been processed

Off-by-One Errors

Typical mistake:

for i := 0; i <= len(a); i++ { // wrong

Correct:

for i := 0; i < len(a); i++ {

Reason:

valid indices: 0 to len(a)-1

Empty Input

Always check before accessing elements.

if len(a) == 0 {
	return
}

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

Single Element

Some algorithms assume at least two elements.

Example:

if len(a) == 1 {
	return a[0]
}

Two-pointer algorithms must handle:

l == r

depending on whether a single element is valid.

Two Pointers Boundaries

Opposite-end pattern:

for l < r {
	...
}

Same-direction pattern:

for r < n {
	...
}

Invariant:

l and r always remain within [0, n]

Mistake:

using l <= r when logic requires two distinct elements

Sliding Window Boundaries

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

Example with inclusive:

for r := 0; r < n; r++ {
	for invalid {
		l++
	}
}

Invariant:

window contains elements from l to r inclusive

Common error:

mixing r-l and r-l+1 inconsistently

Matrix Boundaries

Check both dimensions:

if 0 <= r && r < rows && 0 <= c && c < cols {

Mistake:

using rows for both dimensions

Prefix Arrays

Prefix array size is n + 1.

p := make([]int, n+1)

Access pattern:

p[0] = 0
p[i] = sum of first i elements

Range query:

sum := p[r] - p[l]

Mistake:

using p[r-1] or mixing inclusive/exclusive conventions

Difference Arrays

For half-open updates [l, r):

d[l] += x
d[r] -= x

For inclusive [l, r]:

d[l] += x
d[r+1] -= x

Mistake:

accessing d[r+1] when r is already the last index without extra space

Binary Search Boundaries

Two standard forms:

Lower Bound

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

Invariant:

[l, r) always contains the answer

Upper Bound

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

Mistake:

using inconsistent updates leads to infinite loops

Loop Termination

Ensure progress in every iteration.

Bad:

for l < r {
	if condition {
		l++
	}
}

If condition is false, loop does not progress.

Correct:

for l < r {
	if condition {
		l++
	} else {
		r--
	}
}

Sentinel Values

Sentinels simplify boundary logic.

Example:

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:

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.