# 1.25 Common Failure Modes

Even when the algorithmic idea is correct, implementations fail in predictable ways. These failures are not random. They arise from mismatches between the specification, the model, and the code. Recognizing these patterns early reduces debugging time and prevents subtle errors.

## Problem

You have an implementation that behaves incorrectly or inconsistently, and you need a systematic way to identify likely causes.

## Solution

Check the implementation against a small set of known failure categories. Most bugs fall into one of these groups.
## Boundary Errors

These occur when indices, intervals, or loop limits are incorrect.

Typical cases:

```text
Using left < right instead of left <= right
Forgetting to process the last element
Off-by-one errors in prefix or suffix loops
Mixing inclusive and half-open intervals
```

Example:

```text
for i = 0 to n:
```

This accesses `A[n]`, which is outside the array.

Correct:

```text
for i = 0 to n - 1:
```
## Incorrect Invariant

The code updates state in a way that violates the intended invariant.

Typical cases:

```text
Updating state before checking a condition
Forgetting to maintain a relationship between variables
Using stale values after mutation
```

Example:

```text
best = 0
```

for maximum subarray sum. This breaks correctness when all values are negative.
## Missing Edge Cases

The algorithm works on typical inputs but fails on boundary inputs.

Typical cases:

```text
Empty input not handled
Single-element input misprocessed
Duplicate values ignored
Degenerate graph or tree not handled
```

Example:

Binary search on an empty array without checking length.
## Wrong Data Structure

The algorithm assumes certain operations are cheap, but the implementation uses a structure where they are expensive.

Typical cases:

```text
Using list instead of hash set for membership
Using array where frequent insertions are needed
Using recursion where stack depth is too large
```

This may not break correctness, but it breaks complexity guarantees.
## Hidden Complexity Blowup

The code contains operations whose cost is larger than expected.

Typical cases:

```text
Sorting inside a loop
Copying arrays repeatedly
Using expensive string concatenation
Nested recursion without memoization
```

Example:

```text
for i = 0 to n - 1:
  sort(A)
```

This changes time from (O(n \log n)) to (O(n^2 \log n)).
## Integer Overflow

Arithmetic exceeds the numeric limits of the chosen type.

Typical cases:

```text
mid = (left + right) // 2
sum exceeds 32-bit range
multiplication overflows before comparison
```

Example:

Using 32-bit integers for values that may reach (10^{15}).
## Floating-Point Errors

Comparisons on approximate values produce incorrect decisions.

Typical cases:

```text
Using x == y for computed floats
Comparing values with accumulated rounding error
Geometry predicates using floating arithmetic without tolerance
```
## State Mutation Bugs

Shared or mutable state is modified incorrectly.

Typical cases:

```text
Reusing arrays across recursive calls
Forgetting to undo changes in backtracking
Modifying a list while iterating over it
```

Example:

DFS with a global visited set not reset between runs.
## Incorrect Termination

Loops or recursion do not terminate or terminate too early.

Typical cases:

```text
Loop condition never becomes false
Recursive call does not reduce problem size
Stopping before processing all candidates
```

Example:

```text
while left < right:
  left = mid
```

If `mid == left`, the loop does not progress.
## Wrong Output Contract

The algorithm returns a value that does not match the required output format.

Typical cases:

```text
Returning cost instead of path
Returning index instead of value
Returning 0-based index when 1-based is required
Returning one solution when multiple must be listed
```
## Testing Blind Spots

The algorithm appears correct because tests are insufficient.

Typical cases:

```text
Testing only random inputs
Missing adversarial cases
Using the same flawed logic in baseline and optimized code
Not testing extreme values
```
## Debugging Strategy

When an algorithm fails, use this sequence:

```text
1. Re-check the problem statement and output contract.
2. Test on smallest inputs and edge cases.
3. Print or inspect state at each step.
4. Verify invariants explicitly.
5. Compare with a brute force baseline.
6. Check numeric limits and types.
7. Review loop boundaries and termination.
8. Isolate the smallest failing input.
```

This process narrows the error quickly.
## Failure Pattern Summary

| Category            | Symptom                               |
| ------------------- | ------------------------------------- |
| Boundary error      | Crashes or incorrect last element     |
| Invariant violation | Works on some inputs, fails on others |
| Missing edge case   | Fails on small or extreme inputs      |
| Wrong structure     | Slow or times out                     |
| Complexity blowup   | Works on small input, fails on large  |
| Overflow            | Incorrect large values                |
| Floating error      | Inconsistent comparisons              |
| Mutation bug        | Non-reproducible behavior             |
| Termination bug     | Infinite loop or premature exit       |
| Output mismatch     | Format or value incorrect             |
## Takeaway

Most algorithmic bugs follow a small set of patterns. By checking boundaries, invariants, data structures, numeric limits, and output contracts systematically, you can diagnose and fix errors without guesswork.