Loop Invariants Part 1 — The One Concept That Makes Algorithms Click

Topics covered: loops, accumulators, hash maps, lookup patterns, data structure → invariant mapping

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 that makes every loop make sense: the invariant.

Once you see it, you can't unsee it. It's in every algorithm you've already written. You were just never told to look.

So here's the invariant — not as a formal proof, but as a tool. One you can use immediately, and understand completely by the end of this post.

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 loop → the update becomes obvious. When code fails: find the step where the invariant broke. That's your bug.

---

The Promise | What It Actually Is

An invariant is a fact that stays true at every step of your loop.

That's it. No formal math. No proofs. It's a promise your code makes to itself — and keeps — on every single iteration.

Formally: true before the loop, preserved by every iteration, implies correctness at termination. An invariant is a loop-level induction hypothesis — the same reasoning that proves mathematical theorems, applied to code.

If you can state the invariant, you understand why the algorithm works. If you can't, you're just memorizing code.

In formal CS, invariants are how algorithm correctness is proved. In practice, they're how you write the algorithm and debug the loop. Same tool, two modes.

---

The Cashier | 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 during this process, 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 49 bills: $1,180 + $20    = $1,200  ✓
After 50 bills: $1,200 + $0     = $1,200  ✓

You never had to verify the total mid-count. The invariant guaranteed it.

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 final result is correct. (This only works if each bill is counted correctly — the invariant assumes each step executes as written, just like your code does.)

---

The First Trace | findMax in Code

Find the maximum value in an array:

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 — in production, guard with if (nums.length === 0) throw new Error("Empty array") before reading nums[0]. This post keeps that out to stay focused on the invariant, not error handling.

The invariant: At the start of each iteration i, max holds the largest value in nums[0..i-1].

What does nums[0..i-1] mean?

Shorthand for "all elements the loop has already visited." At i=1, that's [nums[0]]. At i=3, that's [nums[0], nums[1], nums[2]]. When the loop finishes at i = nums.length, that's the entire array.

At the start of iteration i, you've visited 0 through i-1. You haven't touched i yet — so the invariant can only speak about 0..i-1. You'll see this notation in every algorithm in this post.

Let's trace it with nums = [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]  ✓

At every step, the invariant held. When the loop finishes, max holds the largest of the entire array.

Not because the tests passed. Because the logic was sound.

Complexity: O(n) time, O(1) space.

A mental picture that works for every loop:

┌──────────────────┬────────┬──────────────────┐
│    processed     │   i    │   unprocessed    │
│    0 .. i-1      │        │   i+1 .. n-1     │
└──────────────────┴────────┴──────────────────┘
         ↑                           ↑
  invariant covers              not yet seen
   this window

The invariant always describes what you know about the left side. The loop body earns each step by updating that window correctly.

---

The Beginner Trap | What Most People Do

Skip the invariant and go straight to code.

"I'll just figure out the algorithm, write it, and test it."

It works on easy problems. Green checkmark. Move on.

Then you hit mediums. Binary search variants, sliding window with conditions, two pointers on unsorted arrays. And you get stuck — not because you're bad at coding, but because you can't debug what you can't explain. You don't know what should be true at each step, so you can't tell where things went wrong.

• You write code that "almost works" but fails edge cases
• You fix one case and break another
• You copy a solution and it feels like magic you'll forget by tomorrow

The invariant breaks this cycle. When your code fails, you don't guess — you check: "At which step did the invariant break?" That's your bug. Every time.

It's not a superpower. It's just knowing what you're doing.

---

The Decision Tree | Data Structures Shape Invariants

Here's a trick most tutorials skip: the data structure you choose determines the invariant you can write — and the invariant you need to write drives the data structure choice. They aren't separate decisions. They're the same decision, approached from two directions: problem → what must be remembered → data structure → what invariant is expressible.

Variable → "best/total so far"

When your data structure is a single variable, the invariant is always about accumulated state:

variable holds the [best/total/count] of nums[0..i-1]

Data structure	Invariant shape	Example problem
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)
count: number	count = occurrences of target in nums[0..i-1]	Count occurrences

When to reach for this: The problem asks for a single value — total, maximum, minimum, count — across the whole array.

Set → "have I seen this?"

When your data structure is a Set, the invariant is about membership:

seen contains every [value] from nums[0..i-1]

Data structure	Invariant shape	Example problem
Set<number>	seen has all values at nums[0..i-1]	Contains Duplicate (#217)
Set<string>	seen has all chars in window [left..right]	Longest Substring Without Repeating (#3)

When to reach for this: The problem asks "does X exist?", "are all elements unique?", or "have I encountered X before?"

Map → "what do I know about this?"

When your data structure is a Map, the invariant is about associated data:

map contains every [value → associated info] from nums[0..i-1]

Data structure	What the value stores	Invariant	Example problem
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)

When to reach for this: The problem asks "find something that matches X", "count how many", or "group by property."

Two Pointers → "the answer is between here"

When your data structure is two index pointers (left, right), the invariant is about the search space:

Pointer movement	Invariant	Example problem
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 eventually meet slow	Linked List Cycle (#141)

When to reach for this: Input is sorted, you're looking at subarrays/substrings, or you need to shrink/grow a window.

Queue → "all nodes at this distance first"

When your data structure is a Queue, the invariant is about processing order:

Invariant shape	Example problem
All nodes at distance d are visited before any node at distance d+1	BFS Shortest Path
Every node in the queue is reachable and unvisited	Number of Islands (#200)

When to reach for this: The problem asks for shortest path, minimum steps, or layer-by-layer traversal.

The Pattern

"I need to accumulate a value"         → variable     → invariant: "X so far"
"I need to check if something exists"  → Set          → invariant: "seen so far"
"I need to look up associated data"    → Map          → invariant: "known so far"
"I need to narrow a search space"      → two pointers → invariant: "answer is between"
"I need to process level by level"     → Queue        → invariant: "all at distance d first"

Read a new problem. Ask: "What do I need to remember as I iterate?" The answer tells you the data structure, and the data structure tells you the invariant.

If you can't write a clean invariant, you picked the wrong data structure. That vague feeling — "it holds... something about what I've seen so far?" — isn't a wording problem. It's a structure problem. Switching the structure changes what invariant is even expressible.

New to invariants? Start with Variable, Set, and Map — all three follow the same template: "[structure] holds [what] for elements 0..i-1." Two Pointers and Queue use a different invariant shape (search space, not accumulated state). Get the first three feeling natural before tackling those.

---

The Hunt | How to Find It

Ask yourself at the start of each loop iteration:

"What is true about my variables right now?"

Three steps:

1. Before the loop starts — what's true? (The starting point.)
2. After each iteration — is that thing still true? (Check at least two steps — bugs often hide on the first.)
3. When the loop ends — does the invariant + exit condition = the answer?

If all three work, you found it. The invariant is always hiding in the answer to "what must be true here for this to be correct?"

3 failure modes. Most loop bugs are one of these:

• Check 1 fails → bad initialization (wrong before the loop)
• Check 2 fails → wrong update (invariant breaks mid-loop)
• Check 3 fails → wrong termination (invariant holds, but doesn't cover the full answer)

Most bugs are invariant violations disguised as edge cases. This triages them.

Example with Two Sum:

Quick context: you're looking for two numbers that add up to a target. The complement is target - number — the other value needed to form the pair. Two Sum uses a Map storing value → index, so you can return both indices when a match is found.

1. Before loop: seen (a Map<number, number>) is empty → contains all value → index pairs before index 0 → that's nothing → ✓
2. After each iteration: ask "is the complement of nums[i] already in seen?" If yes — early return. If no — add nums[i] → i to map. Now map contains all pairs for 0..i → ✓
3. When the loop ends: if no pair was found across the entire array, none exists. The invariant (seen holds value → index for all nums[0..i-1]) combined with the exit guarantees every combination was checked → ✓

All three checks pass. The invariant is real. (The full Two Sum solution comes after the three prerequisite posts — that's where it belongs.)

---

In Action | Seeing It Applied

The Decision Tree tells you which data structure to pick. The Hunt tells you how to verify the invariant. Here's what the live thought process looks like — picking a structure and watching the invariant fall out. (Full implementations — with loop context, edge cases, and traces — are in the dedicated posts linked in the footer.)

Valid Anagram (#242) — Map invariant

"Are two strings anagrams?" → I need to track whether each character's frequency matches between s and t. That's a difference per character. → Map.

Invariant: At the start of iteration i, counts[char] = frequency of char in s[0..i-1] minus frequency in t[0..i-1].

If all counts are 0 at the end → every character matched → anagram. The invariant tells you exactly why: at every step, counts tracks the net imbalance between what s has provided and what t has consumed. O(n) time, O(1) space for bounded character sets (26 lowercase letters); O(k) for arbitrary characters.

Maximum Subarray / Kadane's (#53) — Two simultaneous variables

"Find the contiguous subarray with the largest sum." → I need the best subarray ending at my current position, and the best anywhere. Two separate things. Two variables, two invariants.

Invariant 1: At the start of iteration i, maxEndingHere = max subarray sum ending at index i-1 (must include nums[i-1])
Invariant 2: At the start of iteration i, maxSoFar = max subarray sum anywhere in nums[0..i-1]

This is the first time you'll track two truths at once. Treat them independently — 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. It's the only pattern in this post requiring two simultaneous invariants. O(n) time, O(1) space.

Binary Search — Two-pointer invariant

"Find target in a sorted array." → Sorted + narrowing search → two pointers.

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 invariant — updating left or right incorrectly so the target falls outside the window. The < vs <= exit condition debate isn't a style choice — it's a boundary decision: an inclusive upper bound (right is still a valid candidate) uses <=; an exclusive one (right has already been eliminated) uses <. The invariant tells you which boundary you're maintaining, and that tells you which condition is correct. O(log n) time, O(1) space.

Two Sum II — Sorted (#167) — Two-pointer invariant

"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 any index ≥ left — the array is sorted, so every element from left onward is at least as large. Moving right down can't skip a valid pair; the invariant still holds. Symmetrically, when sum < target, nums[left] is too small to pair with any index ≤ right — moving left up is safe for the same reason. On an unsorted array, that reasoning collapses — you can't make that guarantee. O(n) time, O(1) space. (This applies to the inward pair-sum pattern. Fast + slow pointers use a different invariant and work on unsorted linked lists.)

The Pattern Across All Four

Every algorithm in this post — and every loop you'll ever write — follows the same skeleton:

state:     the data structure (variable, set, map, pointers)
invariant: what that structure promises to hold at each step
update:    the operation that maintains the invariant as i advances

Every time, same thought process:

1. "What do I need to remember?" → picks the data structure (state)
2. State the invariant using that structure's template
3. The invariant dictates the update — the algorithm writes itself

You didn't figure out the code. You reasoned your way to it. That's the difference.

---

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 (BFS)

2. Write the invariant using this template:
   "[data structure] contains/holds [what] for elements [0..i-1]"

   Note: this template works for variable, Set, and Map.
   For two pointers use: "the answer, if it exists, is within [left..right]"
   For Queue (BFS) use: "all nodes at distance d are processed before any at distance d+1"

3. Verify with 3 checks:
   ✓ True before the loop?
   ✓ Still true after each iteration?
   ✓ Invariant + loop exit = answer?

If you can do steps 1–3 before writing code, the code writes itself. Most people can't. Now you can.

---

Practice These First | Before Two Sum

Two Sum (#1) is the most famous easy problem — but it combines three separate tricks. Solve these three first and Two Sum becomes obvious.

Problem	What it teaches you	The invariant	How it connects to Two Sum
Running Sum (#1480)	Loop with an accumulator	sum = total of nums[0..i-1]	Teaches the invariant mindset — "what's true at each step?"
Contains Duplicate (#217)	Hash set lookup: "have I seen this before?"	seen contains all elements at nums[0..i-1]	The exact same question Two Sum asks — just simpler
Valid Anagram (#242)	Hash map as a frequency counter	counts[char] = freq of char in s[0..i-1]	Using hash maps for more than existence — counting and comparing

Why this path works:

Two Sum = Running Sum's invariant thinking
        + Contains Duplicate's lookup pattern
        + Valid Anagram's hash map skills

"my map contains everything seen so far"     ← invariant  (from Running Sum)
"is the complement in the map?"               ← lookup     (from Contains Duplicate)
"store value → index pairs"                   ← hash map   (from Valid Anagram)

When you've practiced these three building blocks separately, Two Sum isn't a "trick." It's the natural combination of skills you already have.

---

Part 1 of the Loop Invariants series. Part 2 covers what to do when you can't find the invariant (reverse-engineer from the exit condition), a 3-check system that pinpoints bugs by category, and three concrete bug examples each caught by a different check. Next in the series: Running Sum (#1480), Contains Duplicate (#217), and Valid Anagram (#242).