How to prove correctness of algorithms

Learn the two-step method for algorithm correctness proof in interviews. Verify the loop invariant, then check edge cases. Walkthrough included.

10 minutes

Advanced

What you will learn

What algorithm correctness proof means in an interview context

The two-step verification method interviewers expect

How to prove the sliding window algorithm step by step

Common mistakes that make correctness arguments fall apart

How do you know your algorithm actually works? Not just "it passes the test cases" or "it seems right on the example I traced," but truly correct for every possible input before you've typed a single line of code. Algorithm correctness proof is the skill of answering that question on the spot, and most engineers freeze when an interviewer actually asks it.

⚡TL;DR

Algorithm correctness proof in interviews means two things. State what property your loop maintains (the invariant) and verify it holds at every step, then confirm edge cases terminate correctly. It's structured reasoning you can practice, not formal math.

What proof of correctness means in interviews

Most engineers hear "prove your algorithm is correct" and think back to their discrete math course, with induction proofs and formal notation on the blackboard. But that's not what interviewers are asking for.

Algorithm correctness proof in an interview isn't a formal mathematical proof. It's the ability to state your algorithm's invariant, trace it on a concrete example to verify it holds at each step, and check that edge cases produce the right output.

CS programs spend weeks on formal proof by induction, and that's real mathematics. But the gap between academic proofs and interview proofs is wider than most people realize. The interview version is closer to what a senior engineer does during code review: read the loop, ask "what's true at each iteration?", and mentally check whether that property guarantees the right answer. They share the same root concept but the execution is different entirely.

ℹ️ Info

An invariant is a property that stays true before and after every iteration of your loop. If you can state the invariant clearly, trace it through the algorithm, and show it produces the correct answer when the loop ends, you've proven correctness for that algorithm.

When an interviewer says "convince me this works," they want three things: the property your loop maintains, evidence it holds at every step, and confirmation that the final state gives the right answer. Most candidates can't do this clearly. The ones who can get noticeably different reactions from the interviewer.

The two step method: Invariant and edges

The whole method comes down to two checks.

Step 1: Identify and verify the loop invariant

Before tracing any code, state what's supposed to be true at the start of each iteration. This is the claim your algorithm depends on. Then trace through 3-4 iterations manually, checking that the property holds after each one.

Step 2: Check boundary and termination conditions

The invariant tells you the loop body is correct. The boundary check tells you the algorithm starts correctly (initialization), ends correctly (termination produces the right output), and handles degenerate inputs. Edge cases live here, things like empty input, single element, all identical values, and maximum-size arrays.

Most engineers skip step 1 entirely. They jump straight to tracing with a specific input and checking the output, which is testing rather than proving. Testing tells you it works for that input. The invariant tells you it works for every input.

“Testing tells you it works for that input. The invariant tells you it works for every input.”

The distinction interviewers are looking for

The difference matters practically. An engineer who can say "my sliding window maintains the sum of exactly K elements at each step, and I can show you the mechanism" gives the interviewer confidence that the solution generalizes. An engineer who says "I traced it and got the right answer for [3,1,4,1,5]" leaves the interviewer wondering about inputs they didn't trace.

Proving the sliding window

Take the classic fixed sliding window problem: given an array of integers and a window size K, find the maximum sum of any contiguous subarray of length K. The algorithm in Python:

Python

Now apply the two-step method to prove it's correct.

Step 1: Identify and verify the loop invariant

The invariant is that at the start of each iteration, window_sum equals the sum of elements in the current window of K elements.

Trace it on the array [2, 1, 5, 1, 3, 2] with K = 3 to verify.

Before the loop, window_sum = 2 + 1 + 5 = 8. The window covers indices 0-2, and the invariant holds.
At iteration 3, window_sum = 8 + 1 - 2 = 7. The window covers indices 1-3. The actual sum of [1, 5, 1] is 7, so the invariant holds.
At iteration 4, window_sum = 7 + 3 - 1 = 9. The window covers indices 2-4. The actual sum of [5, 1, 3] is 9, and the invariant holds again.
At iteration 5, window_sum = 9 + 2 - 5 = 6. The window covers indices 3-5. The actual sum of [1, 3, 2] is 6, confirming the invariant.

At every step, the invariant holds. The update adds the new element entering the window and subtracts the element leaving it. That's why the invariant is maintained, not just that it is.

Step 2: Check boundary and termination conditions

For initialization, the code computes the sum of the first K elements directly, so the invariant holds before the loop starts. For termination, the loop runs from K to the end of the array, so the final window covers the last K elements and max_sum has tracked the maximum across all windows.

The last step is checking edge cases. What if K equals the array length? The loop doesn't execute, and the initial window_sum is already the answer. What if the array contains all negative numbers? The invariant doesn't depend on sign, so it still holds. What if K is 1? Each window is a single element, and the update correctly shifts by one position.

That's a complete algorithm correctness proof for an interview. You stated the invariant, showed it holds at each step, explained the mechanism behind the update, and confirmed initialization and termination.

💡 Tip

Practice articulating your invariant out loud before tracing. If you can't say it in one sentence, your algorithm might be more complex than you realize, or you haven't fully understood what it's doing.

Where it goes wrong

Here are five ways correctness arguments fall apart in interviews, and all of them are avoidable.

"It works on my example" fallacy: Tracing one input and getting the right answer isn't a proof because it's a single data point. The invariant is what bridges the gap from one example to all inputs.
Not articulating the invariant: You probably have an intuitive sense of what your algorithm does at each step. But when an interviewer asks "why does this work?", vague hand-waving at the code doesn't land. The invariant forces you to turn that gut feeling into a checkable claim.
Skipping boundary checks: The invariant covers the loop body, but boundaries need separate verification. You need to confirm what happens before the loop starts, what happens after it ends, and what happens with degenerate inputs like empty arrays or single elements.
Proving termination, not correctness: Saying "the loop runs N times and exits" proves the algorithm terminates, but it says nothing about whether the output is right. Termination and correctness are separate properties, and you need both.
Overcomplicating the argument: If your correctness reasoning takes three paragraphs to explain, your algorithm might be too complex. Simpler algorithms have simpler invariants. That's one reason interviewers prefer elegant solutions.

One more thing worth mentioning: if you only practice correctness reasoning on sliding window problems, the skill won't transfer cleanly to graphs or DP. Rotating between different patterns and different verification tasks (stating invariants, tracing examples, checking edge cases) builds much stronger transfer than drilling one category.

Two halves of the same skill

Correctness reasoning and mental dry running are two halves of the same skill. The dry run gives you the trace. The invariant gives you the claim to verify against that trace. Practice them together and you'll build the kind of algorithmic intuition that transfers across problem types.

The same idea shows up in DP. When you derive a recurrence relation, you're implicitly stating an invariant: dp[i] represents the optimal answer for the first i elements. Proving that recurrence correct uses the same two-step process. If you're working through DP preparation, the memoization vs tabulation comparison covers how this reasoning transfers to both top-down and bottom-up solutions. The broader progression from understanding algorithms to proving they work to applying them under pressure is covered in the complete algorithmic intuition guide. You don't need mathematical talent for this, you need practice.

Codeintuition's learning path embeds proof of correctness directly into pattern lessons. The understanding lesson for the fixed sliding window walks through why the window update preserves the invariant before you ever see a problem. That verification skill, practiced on every pattern across 16 courses and 75+ explicitly taught patterns, is exactly what we've been talking about.

Six months from now, an interviewer asks you to explain why your graph traversal terminates correctly. Instead of fumbling, you state the invariant, that each node is visited exactly once because the visited set grows monotonically and the graph is finite. Then you trace two iterations, confirm the base case, and the interviewer nods. That confidence didn't come from solving more problems. It came from practicing verification as a separate, trainable skill.

The free Arrays and Singly Linked List courses cover 85 problems across 15 patterns. You don't need to pay or sign up for a trial. Start with the sliding window invariant from this article and see whether stating it out loud changes how you tackle the next unfamiliar problem.

Do you want to master data structures?

Try our data structures learning path made of highly visual and interactive courses. Get hands on experience by solving real problems in a structured manner. All resources you would ever need in one place for FREE

Start Learning

No. Interviewers don't expect induction proofs or formal notation. They want you to state what property your algorithm maintains (the invariant), show it holds through a few iterations, and confirm edge cases work. It's closer to a senior engineer code review than a discrete math exam.

Testing checks specific inputs and outputs. Correctness proof through invariants explains why your algorithm works for all valid inputs. When you trace and verify the invariant, you're showing the mechanism that guarantees correctness rather than just demonstrating one successful run.

Pick any algorithm you already know and state its loop invariant in one sentence. If you can't do it, you understand the code but not the reasoning behind it. Start with simple patterns like two pointers and sliding window, then move to more complex ones like graph traversal and dynamic programming. Varying the patterns you practice on builds stronger transfer than drilling a single category. Even ten minutes a day of invariant articulation practice makes a measurable difference over a few weeks.

State a separate invariant for each loop. The output of the first loop's invariant becomes the starting assumption for the second loop. For nested loops, the outer invariant describes the macro property and the inner invariant describes what each inner pass accomplishes. Trace the inner loop fully before stepping the outer loop forward. This layered reasoning is especially important for two-pass algorithms like those used in prefix sum problems.

The payoff grows with difficulty. Easy problems often have straightforward invariants that are obvious from the code, so the skill matters less there. Medium and hard problems have subtler invariants where the "why does this work" question separates candidates who memorized the pattern from candidates who genuinely understand it.