Off-By-One Errors — Survival Guide
Off-by-one errors (also called fencepost errors or OBOE) are the bug class that haunts every programmer regardless of experience. They are the difference between writing
< nand<= n, betweenrange(n)andrange(n + 1), betweenmidandmid - 1, between depth-from-root and depth-from-leaf. The boundary between two regions is where bugs live. This is a reference card: the most common sites of off-by-one bugs, with the bug, the fix, and the reasoning, organized by area. Memorize the patterns; trace by hand on the smallest non-trivial input; and use loop invariants explicitly when in doubt.
1. Intuition — The Fencepost Problem
Why does this name keep showing up? Because the fundamental confusion has a centuries-old physical analogue: how many fenceposts to span 100 feet of fence with posts every 10 feet? If you compute 100 / 10 = 10, you’re wrong — the correct answer is 11 (the posts at the 0-foot and 100-foot ends both count). One more post than gaps. The off-by-one is in deciding whether to count intervals or boundaries.
In code, the fencepost shows up everywhere two adjacent things have a boundary between them. Indices vs counts: if you have n items in an array, the indices run 0, 1, ..., n-1 — that’s n items, but the highest index is n-1, not n. Inclusive vs exclusive endpoints: a range [a, b] has b - a + 1 items; a range [a, b) has b - a. Depth from root vs leaves: a tree with one node has depth 0 from the root and depth 0 from the leaf — but the same node, in a tree of three, has depth 0 from root and depth 1 from leaf, depending on which side of the boundary you start counting.
Off-by-one is the bug class where humans are most-reliably wrong. The fix is not “be more careful” (you tried; it didn’t work). The fix is systematic: pick a convention and use it everywhere; verify by tracing the smallest non-trivial input by hand; state loop invariants explicitly. This note collects the patterns and the standard remedies.
2. Tiny Worked Example — The Off-By-One That Catches Everyone
How many integers are in the range 1, 2, ..., 100?
The answer is 100. Easy.
How many integers are in the range 5, 6, ..., 100?
Most people compute 100 - 5 = 95. Wrong — the answer is 96. The correct formula is 100 - 5 + 1 = 96 because both endpoints are inclusive: positions 5, 6, 7, ..., 100. The “+1” is the fencepost adjustment.
If the range were half-open [5, 100) — meaning 5, 6, ..., 99 — the answer is 100 - 5 = 95. Now the simple subtraction is correct, because half-open ranges don’t double-count the endpoint.
This is why half-open intervals [a, b) are the C/C++/Python convention: subtraction gives the count directly, no fencepost adjustment. (See Dijkstra’s EWD 831, “Why numbering should start at zero”, 1982 — a one-page essay arguing that half-open [0, n) is the natural choice and reduces the off-by-one rate.)
3. The Master Reference Table — Common Off-By-One Sites
This is the most-printed section of the note. Each row is a common bug pattern, the standard fix, and the underlying reasoning. Keep this open while writing index-heavy code.
| Area | Bug pattern | Fix | Reasoning |
|---|---|---|---|
| Array indexing | for i in range(1, n) when iterating all elements | for i in range(n) (start at 0) | Arrays are 0-indexed; valid indices are 0..n-1, not 1..n |
| Array indexing | arr[n] to access “last element” | arr[n - 1] or arr[-1] | Last index is n - 1 (n elements, indices 0..n-1) |
| Array indexing | for i in range(n + 1) when iterating elements | for i in range(n) | range(n+1) yields 0..n, which is n+1 values, one too many |
| Loop bounds | for i in range(1, n + 1) to do “n iterations” | Either keep, or use range(n) and adjust formula | Both produce n iterations but the index range differs |
| Half-open vs closed | Using [lo, hi] (closed) and hi = mid - 1 ↔ Using [lo, hi) (half-open) and hi = mid mixed in same code | Pick one convention and stick with it | Mixing styles is the #1 binary search bug |
| Binary search closed | while lo < hi: with closed-interval invariant | while lo <= hi: | Closed [lo, hi] requires <= to include the endpoint case |
| Binary search half-open | while lo <= hi: with half-open invariant | while lo < hi: | Half-open [lo, hi) excludes hi, so < is right |
| Binary search closed | lo = mid; hi = mid when narrowing (closed) | lo = mid + 1; hi = mid - 1 | In closed-interval search, the midpoint has been checked; exclude it next |
| Binary search half-open | hi = mid - 1 for half-open | hi = mid | In half-open, hi is already exclusive; no -1 needed |
| Sliding window | right - left for window length when both inclusive | right - left + 1 | Closed window [left, right] of length 5 has right - left = 4 |
| Sliding window | right - left + 1 for half-open window [left, right) | right - left | Half-open windows have a clean length formula |
| String slicing (Python) | s[0:n - 1] to get first n characters | s[0:n] (or s[:n]) | Python slices are half-open; s[a:b] has b - a characters |
| Two-pointer | for i in range(n - 1): then arr[i+1] (last access skipped) | If iterating pairs, range(n - 1) is correct; if iterating elements, range(n) | Trace the loop and check what’s accessed |
| Tree depth (root = 0) | Returning depth + 1 from a leaf | Return 0 for null, max(left, right) + 1 | Convention: empty tree depth = 0, single-node tree depth = 1 or 0; check spec |
| Tree depth (leaf = 0) | Confusing with root-depth | Decide convention up front and document | Two valid conventions; mixing them is bug #1 |
| Heap parent/child indexing (1-indexed) | parent = i / 2; left = 2*i; right = 2*i + 1 | Correct for 1-indexed heap | These are the canonical formulas |
| Heap parent/child indexing (0-indexed) | parent = (i - 1) / 2; left = 2*i + 1; right = 2*i + 2 | Correct for 0-indexed | Different formulas; trace by hand on a 5-element heap |
| Inclusive prefix sum | prefix[i] defined as sum of arr[0..i] (inclusive) | Use a prefix[0] = 0 sentinel and prefix[i] = sum of arr[0..i-1] | The sentinel-based half-open form makes range-sum queries cleaner: sum(l..r) = prefix[r+1] - prefix[l] |
| Range-sum query | prefix[r] - prefix[l] when prefix is 0-indexed and inclusive | prefix[r] - prefix[l - 1] | The off-by-one depends on whether you used the sentinel form or not |
| Sieve of Eratosthenes | for j in range(p*p, n) (excluding n) when you want primes up to n inclusive | for j in range(p*p, n + 1) | Half-open vs closed: depends on whether n should be checked |
| Date / time arithmetic | ”5 days from Monday” → reaching Saturday but writing Monday + 5 = Saturday mentally vs. Monday + 5 days = Saturday calendar-wise | Always trace by listing days | Calendar arithmetic is full of off-by-ones |
| Pagination | pages = n / page_size when n doesn’t divide evenly | pages = (n + page_size - 1) / page_size (ceiling) | Ceiling division — last partial page is real |
Substring len | len(s) - 1 confused with len(s) | len(s) is the count; last index is len(s) - 1 | Same array story applied to strings |
| Loop invariant boundary | ”After iteration i, arr[0..i] is sorted” — does that include or exclude arr[i]? | Pick “first i elements are sorted” (means arr[0..i-1]) | Matters for the termination condition |
| Recursion base case | if n == 0: return ... vs if n == 1: return ... | Trace both; many algorithms work for n = 0 (empty input) and you should support it | Avoiding the n = 0 case in code is itself an OBO |
Building output of size n | result = [0] * (n - 1) when expecting n results | result = [0] * n | Allocation off-by-one; surprisingly common |
4. Binary Search — The Canonical Off-By-One Battlefield
Binary search is the single most-failed implementation in interviews because of off-by-one errors. There are two correct conventions — closed-interval and half-open. They both work; mixing them is the bug.
4.1 Convention 1 — Closed Interval [lo, hi]
The search range is arr[lo], arr[lo+1], ..., arr[hi], both ends inclusive. After narrowing, the midpoint has been checked, so we exclude it from the next iteration.
def bsearch_closed(arr, target):
lo, hi = 0, len(arr) - 1 # closed: hi is the LAST valid index
while lo <= hi: # <=: lo == hi is a valid 1-element window
mid = lo + (hi - lo) // 2 # avoid integer overflow (see [[Integer Overflow in Interviews]])
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1 # exclude mid: we just checked it
else:
hi = mid - 1 # exclude mid
return -1 # exit when lo > hi (window is empty)Loop invariant. “If the target is in the array, it is in arr[lo..hi].” Termination: lo > hi ⇒ window is empty; target not present.
4.2 Convention 2 — Half-Open Interval [lo, hi)
The search range is arr[lo], arr[lo+1], ..., arr[hi-1]. The right endpoint hi is one past the last valid index. After narrowing, since hi is exclusive, we don’t subtract 1 when shrinking from the right.
def bsearch_half_open(arr, target):
lo, hi = 0, len(arr) # half-open: hi is ONE PAST the last index
while lo < hi: # <: empty window is lo == hi
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid # NOT mid - 1: hi is exclusive
return -1Loop invariant. “If the target is in the array, it is in arr[lo..hi-1].” Termination: lo == hi ⇒ window is empty.
4.3 The Bug — Mixing the Two
# WRONG: closed-interval initialization with half-open termination
lo, hi = 0, len(arr) - 1 # closed (hi = last valid)
while lo < hi: # half-open (< not <=)
...
# Result: misses the case lo == hi (a single-element window)# WRONG: half-open initialization with closed-interval termination
lo, hi = 0, len(arr) # half-open (hi = one past last)
while lo <= hi: # closed (<= not <)
mid = (lo + hi) // 2
if arr[mid] == ... # IndexError when hi == len(arr) and mid == hiBoth bugs are off-by-one: each function works on most inputs but fails at boundary cases. Pick one convention. Write it the same way every time. Verify by tracing on n = 0, 1, 2 element arrays.
See Binary Search for the comprehensive treatment of binary-search bugs and their fixes.
4.4 Variants With Their Own Off-By-Ones
bisect_left and bisect_right (or lower_bound and upper_bound in C++) — finding the first or last position where an element could be inserted while keeping the array sorted — each have their own subtle off-by-ones. The standard definitions:
lower_bound(arr, x)returns the smallest indexisuch thatarr[i] >= x.upper_bound(arr, x)returns the smallest indexisuch thatarr[i] > x.
The pattern is half-open binary search with a different comparison:
def lower_bound(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def upper_bound(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= x:
lo = mid + 1
else:
hi = mid
return loThe only difference is < vs <=. The off-by-one between these is intentional — getting it wrong gives the wrong bound.
5. Loop Bounds — The Range Family
Python’s range() is a fertile source of off-by-ones. The crucial fact: range(a, b) is half-open, yielding a, a+1, ..., b-1. Length: b - a.
| What you want | Code | Common bug |
|---|---|---|
Iterate n times | range(n) | range(n + 1) — does n + 1 iterations |
Iterate 0 to n inclusive | range(n + 1) | range(n) — misses n |
Iterate 1 to n inclusive | range(1, n + 1) | range(1, n) — misses n |
| Iterate every other index | range(0, n, 2) | range(0, n - 1, 2) — may miss last |
| Iterate backwards | range(n - 1, -1, -1) | range(n, 0, -1) — wrong start, wrong stop |
| Pair adjacent elements | for i in range(n - 1): pair(arr[i], arr[i+1]) | range(n) — arr[i+1] overflows on last iter |
Pair (i, j) with j > i | for i in range(n): for j in range(i+1, n) | range(i, n) — includes j == i (self-pairs) |
The fundamental rule: range(a, b) is half-open. If you want to include the upper endpoint, use b + 1. If you’re indexing into something of size n, the valid indices are range(n) = 0, 1, ..., n-1.
5.1 Reverse Iteration
A common mistake: writing range(n, 0, -1) to “iterate from n down to 0.” This actually iterates n, n-1, ..., 1 — missing 0. The correct form for “iterate from n-1 down to 0” is:
for i in range(n - 1, -1, -1): # n-1, n-2, ..., 1, 0
...The -1 as the stop value is critical: it’s the exclusive lower bound, so the loop stops after iterating 0. Common bug: writing range(n, -1, -1) which iterates n, n-1, ..., 0 — but if you wanted indices into a size-n array, you’ve started at arr[n] (out of bounds!). Trace your reverse-range carefully.
6. Tree-Traversal Off-By-Ones — Depth, Height, and Levels
Trees have two competing depth conventions:
- Depth from root: root is at depth 0; children at 1; etc.
- Height (depth from leaves): leaves at height 0; their parents at 1; root at height = total height.
Both are valid. The off-by-one comes from mixing them.
6.1 Worked Example — Tree Height
def height(node):
if node is None: return -1 # convention 1: empty tree height = -1
return 1 + max(height(node.left), height(node.right))vs.
def height(node):
if node is None: return 0 # convention 2: empty tree height = 0
return 1 + max(height(node.left), height(node.right))The first gives “single-node tree has height 0”; the second gives “single-node tree has height 1.” Both are valid; they differ by 1. Pick one convention for your codebase.
6.2 Worked Example — Tree Depth
def depth(node, target):
"""Return depth of target node from root, or -1 if not found."""
if node is None: return -1
if node == target: return 0 # root-relative: target is at depth 0 from itself
left = depth(node.left, target)
if left >= 0: return left + 1
right = depth(node.right, target)
if right >= 0: return right + 1
return -1The classic mistake: returning 0 for node == target but then computing left + 1 from node.left’s depth, expecting that to be 1 from the parent. It is 1 from the parent’s perspective (one edge down), so the recursive + 1 is correct. Drawing this on a 3-node tree confirms.
6.3 Levels-Have-Off-By-Ones
A common interview question: “How many nodes are at depth k?”
A complete binary tree has 2^k nodes at depth k if root is at depth 0; 2^(k-1) if root is at depth 1. The two conventions disagree by a factor of 2 in the answer formula. Trace by hand on a 7-node tree before claiming.
7. Sliding Window Off-By-Ones — Window Length
A sliding-window problem has two pointers left and right. The key off-by-one is: what is the window length?
| Window definition | Length formula | Comparison for “length k” |
|---|---|---|
Closed [left, right] | right - left + 1 | right - left + 1 == k |
Half-open [left, right) | right - left | right - left == k |
If you use closed-interval intuition (right - left + 1 == k) but maintain a half-open invariant (advancing right past the new element), your length formula is one short. The fix: be explicit about which convention you’ve chosen.
Sliding Window details further — most LeetCode-style sliding-window solutions use closed-interval [left, right] semantics with explicit +1 length formulas.
8. Loop Invariants — The Antidote
The systematic way to avoid off-by-one bugs is to state and verify a loop invariant for every loop. From CLRS Ch. 2.1: a loop invariant is a property that holds before each iteration. You verify three things:
- Initialization — the invariant holds before the first iteration.
- Maintenance — if it holds before iteration
i, it holds before iterationi + 1. - Termination — when the loop exits, the invariant + the exit condition implies what we want.
8.1 Worked Example — Invariant for Binary Search
For half-open binary search:
- Invariant: “If the target is in the array, it is in
arr[lo..hi-1].” - Initialization:
lo = 0, hi = len(arr). The full array isarr[0..len(arr)-1]. The invariant holds (the target, if present, is in the full range). - Maintenance: each iteration narrows the range by either
lo = mid + 1(target is to the right) orhi = mid(target is to the left or atmid). After this update, the target — if present — is still inarr[lo..hi-1]. - Termination:
lo == hi⇒ the range is empty ⇒ the target is not in the array. Return -1.
Stating this invariant explicitly forces you to think about whether hi is inclusive or exclusive, whether the comparison should be < or <=, and whether to set hi = mid or hi = mid - 1. The invariant is the check that catches off-by-ones at design time.
Bentley’s Programming Pearls (2nd ed., Ch. 4) is the canonical accessible introduction to writing correct loops via invariants. Highly recommended.
9. The Famous Real-World Off-By-One — Binary Search Bug in java.util.Arrays
The most-cited industrial off-by-one: in 2006, Joshua Bloch (then at Google) reported that Java’s java.util.Arrays.binarySearch had a bug for 9 years. The line:
int mid = (low + high) / 2;overflows when low + high > Integer.MAX_VALUE (about 2 billion). The fix:
int mid = low + (high - low) / 2; // avoids overflow
// or equivalently:
int mid = (low + high) >>> 1; // unsigned right shiftThis was a bona-fide off-by-one of a different flavor — not in the loop bound, but in the way the midpoint was computed. The lesson: any expression involving sums of indices is suspect, and “one wrong place where two indices are added” can destroy the invariant on huge inputs.
See Integer Overflow in Interviews (planned) for the full treatment.
10. Strategies for Avoiding Off-By-Ones
10.1 Trace by Hand on the Smallest Non-Trivial Example
For binary search: trace on n = 0 (empty), n = 1, n = 2, and n = 3 elements. If your code works on all four cases, it’s probably correct. If it fails on any, you have an off-by-one.
For tree traversals: trace on a 3-node tree. Skewed trees (linked-list-shaped) are also a good test.
For loops: trace the first and last iterations explicitly. What does the loop variable take in each? What does the loop body access?
10.2 Use Loop Invariants
State the invariant before writing the loop. Verify initialization, maintenance, termination. CLRS Ch. 2.1.
10.3 Pick One Convention and Use It Consistently
Half-open [a, b) is the C/C++/Python idiom and gives the cleanest length formulas (b - a, no +1). Closed [a, b] is fine but requires +1 adjustments. Don’t mix them in the same function.
10.4 Use Sentinels
Adding a sentinel (extra element at the boundary) often eliminates off-by-one cases. Examples:
- Prefix sums with
prefix[0] = 0allowsum(l..r) = prefix[r+1] - prefix[l]cleanly. - Linked-list operations with a dummy head node simplify the “delete first node” case.
- String algorithms with a sentinel character (e.g.,
$at end) avoid bound checks in the inner loop.
10.5 Use Helper Functions
Functions like bisect.bisect_left (Python), lower_bound (C++), Arrays.binarySearch (Java) wrap the off-by-one inside a tested library function. Use them rather than re-deriving binary search every time. This is the single most reliable way to avoid binary-search off-by-ones in production code.
10.6 Property-Based Tests
If you’re writing a non-trivial loop, generate random inputs and check the result against a slow-but-obviously-correct reference implementation. A 5-line property test can catch off-by-ones that 100 hand-written test cases miss.
11. Pitfalls — Off-By-Ones in Off-By-Ones
11.1 Confusing Length and Last-Index
A list of n elements has length n and last index n - 1. Don’t write arr[len(arr)] (off the end) or use len(arr) where you meant len(arr) - 1.
11.2 Incorrect Bounds in range() for Reverse
range(n, 0, -1) iterates n, n-1, ..., 1 — missing 0. For n-1 down to 0 inclusive: range(n - 1, -1, -1).
11.3 Mixing 0-Indexed and 1-Indexed Code
Heap problems traditionally use 1-indexed math (parent = i // 2). Most languages use 0-indexed arrays. Either consistently use 1-indexed (waste arr[0]) or convert formulas (parent = (i - 1) // 2).
11.4 Misplacing the +1 in Range-Sum
sum(l..r) on a 0-indexed inclusive prefix sum is prefix[r] - prefix[l-1] (with prefix[-1] = 0 as a special case). The sentinel form prefix[0] = 0, prefix[i] = arr[0] + ... + arr[i-1] gives sum(l..r) = prefix[r+1] - prefix[l]. The +1 placement matters and is convention-dependent.
11.5 Ceiling Division With //
n // m in Python rounds down for positive n, m. For ceiling division: (n + m - 1) // m or -(-n // m). Don’t write n // m + 1 — that’s wrong when m divides n evenly.
11.6 Wrong Comparison Operator at the Boundary
while lo < hi: vs while lo <= hi: is a one-character change with major correctness implications. Each one is correct for one binary-search convention; the wrong one for the other.
11.7 String Indexing in 1-Indexed Languages
If you’re translating a 1-indexed pseudocode (CLRS) into a 0-indexed language (Python), every loop bound must shift by 1. CLRS’s for i in 1 to n becomes Python’s for i in range(n) (with array accesses adjusted). Get the shift wrong and every off-by-one bug becomes possible.
11.8 Substring Length
s[a:b] in Python has length b - a (half-open). So s[a:b] of length 5 has b = a + 5. Beginners often write s[a:a+5-1], off by one short.
11.9 Buffer Overflow in C / C++
char buf[10]; buf[10] = '\0'; is undefined behavior — buf[10] is past the buffer. Valid indices are buf[0]..buf[9]. The C strncpy and friends are notorious for off-by-one buffer overflows.
11.10 Calendar / Time-Span Calculations
“Days between Mon and Wed”: is it 2 or 3? Depends on whether you count both endpoints. (Excel’s DATEDIF and SQL’s DATEDIFF differ from each other by 1 in some configurations.)
12. Diagram — The Half-Open Convention’s Clean Geometry
flowchart LR subgraph "Closed [a, b]" C1["a"] C2["a+1"] C3["..."] C4["b"] C1 --- C2 --- C3 --- C4 LenC["length = b - a + 1"] end subgraph "Half-open [a, b)" H1["a"] H2["a+1"] H3["..."] H4["b-1"] H1 --- H2 --- H3 --- H4 LenH["length = b - a"] Boundary["b is the boundary;<br/>not included"] H4 -.->|"next is b"| Boundary end
What this diagram shows. Two ways to denote a contiguous range. Closed [a, b] includes both endpoints; the count is b - a + 1 (the fencepost adjustment). Half-open [a, b) includes a but excludes b; the count is b - a directly. Half-open is preferred in C/C++/Python because the length formula has no +1, and operations like “split a range at index k” produce two clean half-open sub-ranges ([a, k) and [k, b)) without any boundary-handling. Mixing the two conventions in the same function is the #1 cause of off-by-one bugs in iteration code. The visual takeaway: pick one convention based on language idiom and stick with it consistently.
13. Common Interview Problems Where Off-By-One Bites
| Problem | The off-by-one |
|---|---|
| Binary Search | lo, hi initialization; hi = mid vs hi = mid - 1; < vs <= |
| Sliding Window | window length: right - left + 1 vs right - left |
| Find peak element | bound when checking arr[mid + 1]: must have mid + 1 < n |
| First missing positive | iterating to n: range(n) covers indices 0..n-1; check arr[i] == i + 1 (1-indexed comparison) |
| Trapping rain water | iterate inner cells: range(1, n - 1) not range(n) |
| Spiral matrix | top, bottom, left, right boundaries: each shrinks by 1 per pass; termination when top > bottom or left > right |
| Reverse linked list | the iterative version’s pointer dance: prev = None, curr = head initial values |
| Tree level order BFS | ”next level” detection: store level size before the for-loop, not in the condition |
| Power of two check | n > 0 and (n & (n - 1)) == 0 — the n > 0 is essential since 0 & -1 == 0 would falsely return true |
| Generate parentheses | open and close counts: open == n doesn’t mean we’re done; need close == n too |
| Subarray sum equals K | prefix sum + hash; off-by-one hides in “where is prefix[0] = 0 accounted for” |
14. Open Questions
- Why doesn’t language design force one convention universally? Backwards compatibility plus genuine differences in domain (mathematical notation often uses closed intervals; C-family languages settled on half-open).
- Does Rust’s range syntax
(a..b)vs(a..=b)reduce off-by-one bugs? Empirically, having both syntaxes available makes the choice explicit at the use-site, which probably helps. Verify with bug-rate studies. - Are off-by-ones more common in interpreted or compiled languages? Anecdotally, compiled — buffer overflows in C/C++ are the most catastrophic class of OBOE — but interpreted languages have their own (slicing semantics, comprehension boundaries).
15. See Also
- Binary Search — canonical site for off-by-one battles
- Sliding Window — window-length off-by-ones
- Two Pointers — pairing off-by-ones
- Prefix Sums — sentinel form vs no sentinel
- Tree Traversals — depth-from-root vs depth-from-leaves
- Recursion vs Iteration — base-case off-by-ones
- Integer Overflow in Interviews — sibling pitfall (planned)
- Mutability and Aliasing Bugs — sibling pitfall (planned)
- Big-O Notation — for the complexity vocabulary
- Space Complexity — for analyzing the auxiliary structures
- SWE Interview Preparation MOC