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:

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:

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

Important edge cases:

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:

best = A[0]
current = A[0]

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

Example: Binary Search

Problem:

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

Important edge cases:

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

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:

Tree examples:

Geometry examples:

Invalid Inputs

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

For example:

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:

Reject invalid input.

or:

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:

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

For input:

[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:

mid = (left + right) // 2

A safer form is:

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:

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:

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.