Loop Invariants — The One Concept That Makes Algorithms Click
Most people solve algorithms by trial and error. Write code, run tests, tweak, repeat. Eventually it passes. They move on.
But they can't tell you why it passed. And when the next problem looks slightly different — same pattern, different wrapping — they're back to guessing.
The fix isn't more LeetCode. It's one concept: the invariant.
TL;DR — An invariant is what must stay true at every step of your loop. Pick a data structure → it defines what invariant you can write → verify it holds before, during, and after → the update becomes obvious. When code fails: find the step where the invariant broke. That's your bug.
A Promise Your Code Makes to Itself | The Concept
An invariant is a fact that stays true at every step of your loop.
No formal math. No proofs. Just a promise your code makes — and keeps — on every single iteration.
Formally: true before the loop, preserved by every iteration, implies correctness at termination. In formal CS, invariants are how algorithm correctness is proved. In practice, they're how you write the algorithm and debug it.
If you can state the invariant, you understand why the algorithm works. If you can't, you're memorizing code.
Counting Bills | Before Any Code
Imagine you're counting a drawer of 50 bills totaling $1,200.
You pick up bills one at a time. At any point, this is always true:
Invariant: amount counted + amount remaining = $1,200
After 0 bills: $0 + $1,200 = $1,200 ✓
After 10 bills: $340 + $860 = $1,200 ✓
After 50 bills: $1,200 + $0 = $1,200 ✓
When remaining hits $0, counted must be $1,200. Not probably. Must.
That's the power of an invariant: if it holds at every step and the loop terminates, the result is correct.
The First Trace | findMax in Code
function findMax(nums: number[]): number {
let max = nums[0];
for (let i = 1; i < nums.length; i++) {
if (nums[i] > max) max = nums[i];
}
return max;
}
Note: assumes nums is non-empty — add a length check in production.
The invariant: At the start of each iteration i, max holds the largest value in nums[0..i-1].
nums[0..i-1] means everything the loop has already visited. At i=1, that's [nums[0]]. When the loop finishes, that's the entire array.
Tracing [3, 7, 2, 9, 1]:
Before loop: max = 3 → largest of [3] ✓
i=1: 7 > 3 → max = 7 → largest of [3, 7] ✓
i=2: 2 < 7 → max stays 7 → largest of [3, 7, 2] ✓
i=3: 9 > 7 → max = 9 → largest of [3, 7, 2, 9] ✓
i=4: 1 < 9 → max stays 9 → largest of [3, 7, 2, 9, 1] ✓
The invariant held at every step. When the loop finished, max held the largest of the entire array.
Not because the tests passed. Because the logic was sound.
A mental picture that works for every loop:
┌──────────────────┬────────┬──────────────────┐
│ processed │ i │ unprocessed │
│ 0 .. i-1 │ │ i+1 .. n-1 │
└──────────────────┴────────┴──────────────────┘
↑ ↑
invariant covers not yet seen
The invariant always describes the left side. The loop body earns each step by updating that window correctly.
The Data Structure Decides | The Decision
Here's what most tutorials skip: the data structure you choose determines the invariant you can write. They aren't separate decisions. They're the same decision, approached from two directions.
Ask: "What do I need to remember as I iterate?" The answer gives you the structure. The structure gives you the invariant.
If you can't write a clean invariant, you picked the wrong structure. That vague feeling — "it holds... something about what I've seen so far?" — isn't a wording problem. It's a structure problem.
"Best so far" | Variable
When your data structure is a single variable, the invariant is always about accumulated state.
| Data structure | Invariant shape | Example |
|---|---|---|
sum: number |
sum = total of nums[0..i-1]
|
Running Sum (#1480) |
max: number |
max = largest of nums[0..i-1]
|
Find max (above) |
maxEndingHere: number |
maxEndingHere = max subarray sum ending at i-1
|
Maximum Subarray (#53) |
Reach for this when the problem asks for a single value — total, maximum, minimum, count — across the whole array.
"Have I seen this?" | Set
When your data structure is a Set, the invariant is about membership.
| Data structure | Invariant shape | Example |
|---|---|---|
Set<number> |
seen has all values in nums[0..i-1]
|
Contains Duplicate (#217) |
Set<string> |
seen has all chars in window [left..right]
|
Longest Substring Without Repeating (#3) |
Reach for this when the problem asks "does X exist?", "are all elements unique?", or "have I encountered X before?"
"What do I know about this?" | Map
When your data structure is a Map, the invariant is about associated data.
| Data structure | What the value stores | Invariant | Example |
|---|---|---|---|
Map<number, number> |
value → index |
map has val→idx for nums[0..i-1]
|
Two Sum (#1) |
Map<string, number> |
char → frequency |
map has char counts for s[0..i-1]
|
Valid Anagram (#242) |
Map<string, string[]> |
sorted key → group |
map groups all strings seen so far |
Group Anagrams (#49) |
Map<number, number> |
prefix sum → index |
map has all prefix sums at nums[0..i-1]
|
Subarray Sum Equals K (#560) |
Reach for this when the problem asks "find something that matches X", "count how many", or "group by property."
"The answer is between here" | Two Pointers
When your data structure is two index pointers, the invariant is about the search space.
| Movement | Invariant | Example |
|---|---|---|
| Both inward | Answer is between left and right
|
Two Sum II Sorted (#167) |
| Left chases right | Window [left..right] satisfies constraint |
Sliding Window problems |
| Fast + slow | If a cycle exists, fast will meet slow | Linked List Cycle (#141) |
Reach for this when input is sorted, you're examining subarrays, or you need to grow and shrink a window.
"All at this distance first" | Queue
When your data structure is a Queue, the invariant is about processing order.
| Invariant shape | Example |
|---|---|
All nodes at distance d visited before any at d+1
|
BFS Shortest Path |
| Every node in the queue is reachable and unvisited | Number of Islands (#200) |
Reach for this when the problem asks for shortest path, minimum steps, or layer-by-layer traversal.
The Pattern
"I need to accumulate a value" → variable → "X so far"
"I need to check if something exists" → Set → "seen so far"
"I need to look up associated data" → Map → "known so far"
"I need to narrow a search space" → two pointers → "answer is between"
"I need to process level by level" → Queue → "all at distance d first"
Variable, Set, and Map all follow the same template: "
[structure]holds[what]for elements0..i-1." Two Pointers and Queue use a different shape — they get dedicated posts.
Three Checks + One Question | How to Find It
Ask yourself at the start of each loop iteration: "What is true about my variables right now?"
Then verify three things:
- Before the loop — is it true? (bad initialization if not)
- After each iteration — is it still true? (bad update if not)
- At loop exit — does invariant + exit condition = the answer? (wrong termination if not)
Most loop bugs are one of those three failures. The invariant tells you exactly which one.
When your code breaks, don't guess. Check which step violated the invariant. That's your bug. Every time.
Two Truths at Once | Kadane's Algorithm (#53)
"Find the contiguous subarray with the largest sum."
I need the best subarray ending here, and the best anywhere. Two separate things — two variables, two invariants.
-
Invariant 1:
maxEndingHere= max subarray sum ending at indexi-1 -
Invariant 2:
maxSoFar= max subarray sum anywhere innums[0..i-1]
maxEndingHere answers "what's the best I can do ending here?" maxSoFar answers "what's the best I've ever seen?"
When a problem asks for a "best local" and a "best global" — two variables, two promises, one loop.
The Boundary Decision | Binary Search
"Find target in a sorted array."
Invariant: If target exists, it is always within nums[left..right] — both ends inclusive, both still valid candidates.
Most binary search bugs come from breaking this. The < vs <= exit condition debate isn't a style choice — it's a boundary decision. An inclusive upper bound uses <=. An exclusive one uses <.
The invariant tells you which boundary you're maintaining. That tells you which condition is correct.
Sandwiched Between Two Armies | Two Pointers in Practice
"Find two numbers in a sorted array that add to target." → Sorted + find a pair → two pointers inward.
Invariant: If a valid pair (i, j) exists, then left <= i and j <= right.
When sum > target, nums[right] is too large to pair with anything — move it down. When sum < target, nums[left] is too small — move it up. On an unsorted array, that reasoning collapses entirely.
The invariant tells you why each pointer move is safe. Without it, you're just guessing directions.
All Nodes at This Distance First | Queue in Practice
"Find the shortest path in a grid." → Layer-by-layer traversal → Queue.
Invariant: Every node in the queue is reachable, unvisited, and at distance d — before any node at distance d+1 is processed.
This is why BFS guarantees shortest path. The first time you reach a node, you reached it in the minimum number of steps. The queue ordering makes that true at every step.
Break the invariant — say, by adding already-visited nodes — and BFS silently returns wrong answers.
The Flowchart | Putting It Together
1. What does the problem ask me to find?
└── A single value (sum, max, count)? → variable
└── Does something exist? → Set
└── Find a match / group / look up? → Map
└── Pair in sorted array / subarray window? → two pointers
└── Shortest path / level-by-level? → Queue
2. Write the invariant:
"[structure] holds [what] for elements [0..i-1]"
— or for two pointers: "answer is within [left..right]"
— or for Queue: "all nodes at distance d before d+1"
3. Three checks:
✓ True before the loop?
✓ Still true after each iteration?
✓ Invariant + exit = answer?
If you can do steps 1–3 before writing code, the code writes itself.
Most people can't. Now you can.
Part 1 of the Loop Invariants series. Next: Running Sum (#1480), Contains Duplicate (#217), Valid Anagram (#242).
Top comments (0)