Loop Invariant

A loop invariant is a condition that remains true before and after each iteration of a loop. It is a tool for explaining why loop-based algorithms are correct.

The invariant names what the loop has already accomplished.

Core Idea

A useful loop invariant has three parts. It is true before the loop starts. One loop iteration keeps it true. When the loop ends, the invariant helps prove the final result.

This is useful because many algorithms are loops that slowly grow a known-good region, shrink an unknown region, or maintain a summary of processed data.

Python Example

def prefix_sums(values):
    result = []
    running_total = 0
 
    for value in values:
        running_total += value
        result.append(running_total)
 
    return result

A loop invariant is: after processing i elements, running_total is the sum of the first i elements, and result contains the prefix sums for those i elements.

Common Confusions

A loop invariant is not just any condition inside a loop. It must stay true across iterations and help explain the result.

An invariant can be simple. It does not need to look formal to be useful. The main purpose is to make the reasoning explicit enough that the loop is not just trusted by intuition.

When To Use It

Use a loop invariant when a loop maintains a subtle condition, such as a sorted prefix, a valid window, a current best answer, or a visited set. It is especially helpful when debugging off-by-one errors or explaining binary search.