# 1.10 Edge Cases

Edge cases are valid inputs that sit at the boundary of the specification. They are often small, empty, repeated, extreme, or structurally degenerate. They matter because many algorithms are designed around the typical case, while many bugs occur at the boundary.

An edge case should not be treated as an exception to the problem. It is part of the problem. If the input is allowed by the specification, the algorithm must handle it deliberately.

## Problem

You have an algorithm that works on ordinary examples, but you need to check whether it remains correct on boundary inputs.

## Solution

Classify edge cases before implementation. Use this checklist:

```text
1. Minimum size
2. Empty input
3. Single element
4. Duplicate values
5. All values equal
6. Already sorted input
7. Reverse sorted input
8. Negative values
9. Zero values
10. Maximum allowed values
11. Degenerate structures
12. Multiple valid answers
```

Then decide for each case whether it is valid input, invalid input, or valid but special.

## Example: Maximum Subarray Sum

Problem:

```text
Given an integer array A, return the maximum sum over all nonempty contiguous subarrays.
```

Important edge cases:

| Input          | Expected Result | Reason                              |
| -------------- | --------------: | ----------------------------------- |
| `[5]`          |             `5` | Single element                      |
| `[-3]`         |            `-3` | Nonempty subarray required          |
| `[-5, -2, -8]` |            `-2` | Best subarray may still be negative |
| `[0, 0, 0]`    |             `0` | All values equal                    |
| `[4, -1, 2]`   |             `5` | Ordinary mixed case                 |

A common bug is to initialize the best sum to `0`. That gives the wrong answer for arrays containing only negative numbers if the problem requires a nonempty subarray.

Correct initialization:

```text
best = A[0]
current = A[0]
```

This makes the single-element and all-negative cases part of the normal flow.

## Example: Binary Search

Problem:

```text
Given a sorted array A and a value x, return whether x appears in A.
```

Important edge cases:

| Input             | Target | Expected Result | Reason          |
| ----------------- | -----: | --------------- | --------------- |
| `[]`              |    `3` | `false`         | Empty interval  |
| `[3]`             |    `3` | `true`          | Single match    |
| `[3]`             |    `4` | `false`         | Single nonmatch |
| `[1, 2, 2, 2, 5]` |    `2` | `true`          | Duplicates      |
| `[1, 3, 5]`       |    `0` | `false`         | Below range     |
| `[1, 3, 5]`       |    `7` | `false`         | Above range     |

The loop condition determines whether the empty interval is handled correctly.

```text
left = 0
right = n - 1

while left <= right:
  mid = left + (right - left) // 2
  ...
```

The condition `left <= right` means the current search interval is inclusive. When `left > right`, no candidates remain.

## Degenerate Structures

For graphs, trees, and geometric data, edge cases often come from degenerate structure.

Graph examples:

| Case               | Why It Matters                                         |
| ------------------ | ------------------------------------------------------ |
| No vertices        | Traversal may have no valid start                      |
| One vertex         | Source and target may coincide                         |
| No edges           | Connectivity is usually false except self-reachability |
| Self-loops         | Cycle detection must define whether they count         |
| Parallel edges     | Algorithms must decide whether duplicates are allowed  |
| Disconnected graph | Traversal from one source may not see all vertices     |

Tree examples:

| Case           | Why It Matters                                       |
| -------------- | ---------------------------------------------------- |
| Empty tree     | Recursion needs a base case                          |
| Single node    | Height and diameter definitions differ by convention |
| Long chain     | Recursion depth may become linear                    |
| Complete tree  | Useful ordinary balanced case                        |
| Duplicate keys | Search tree policy must define placement             |

Geometry examples:

| Case                | Why It Matters                           |
| ------------------- | ---------------------------------------- |
| Repeated points     | Convex hull may duplicate vertices       |
| Collinear points    | Orientation tests return zero            |
| Zero-length segment | Intersection logic must handle endpoints |
| Touching polygons   | Boundary inclusion must be specified     |

## Invalid Inputs

Not every edge-like case is valid. The specification should say what happens when input violates assumptions.

For example:

```text
Input guarantee:
  A is sorted in nondecreasing order.
```

If `A` is not sorted, binary search has no correctness obligation unless the problem explicitly requires validation.

There are two common policies:

```text
Reject invalid input.
```

or:

```text
Assume input satisfies the contract.
```

Both are acceptable, but the policy must be clear. Algorithm analysis usually assumes valid input unless stated otherwise.

## Multiple Valid Outputs

Some problems allow more than one correct answer. Edge cases should test that the acceptance condition is flexible enough.

Example:

```text
Given an array, return any index of a maximum value.
```

For input:

```text
[4, 7, 7, 2]
```

both index `1` and index `2` are valid if the problem says "any index." If the problem requires the first maximum, only index `1` is valid. If it requires the last maximum, only index `2` is valid.

This difference changes both tests and implementation.

## Overflow and Numeric Limits

Numerical edge cases often appear even when the algorithmic idea is correct.

For binary search, this midpoint formula can overflow in fixed-width integer languages:

```text
mid = (left + right) // 2
```

A safer form is:

```text
mid = left + (right - left) // 2
```

For sums, products, and counts, check the maximum possible value. An array of length (10^6) with values up to (10^9) can have a sum up to (10^{15}), which does not fit in a 32-bit signed integer.

## Edge Case Testing Recipe

For each algorithm, prepare a small test set with the following structure:

```text
1. Smallest valid input
2. Smallest invalid input, if validation is required
3. One ordinary input
4. Duplicate-heavy input
5. Extreme-value input
6. Input where the answer is at the boundary
7. Input where no solution exists
8. Input with multiple valid answers
```

For binary search, this becomes:

```text
A = [], x = 1
A = [1], x = 1
A = [1], x = 2
A = [1, 2, 2, 2, 3], x = 2
A = [1, 3, 5, 7], x = 1
A = [1, 3, 5, 7], x = 7
A = [1, 3, 5, 7], x = 4
```

## Common Pitfalls

Do not write the main algorithm first and patch edge cases afterward unless the special case is genuinely unavoidable. Most robust algorithms include boundary cases in the invariant.

Do not confuse an empty result with failure. For example, an empty list can be the correct output for "return all matches."

Do not assume duplicates are harmless. Many ordered algorithms change behavior when equal elements appear.

Do not ignore constraints when choosing numeric types. Correct asymptotic complexity does not prevent overflow.

## Takeaway

Edge cases are part of the specification. Treat them as ordinary valid inputs whenever possible, encode them in invariants, and test them directly. A strong algorithm handles boundaries by design rather than by late patching.