How to Prove Your Algorithm Works in a Coding Interview

An interviewer asks you to convince them your algorithm works. You walk through [2, 1, 5, 1, 3, 2] with K=3, get 9, and stop. The interviewer waits. You realise that what you did was test one input, not prove correctness, and you don't have anything else to say.

TL;DR: Proving your algorithm works in interviews isn't a formal induction. It's two things: state what property your loop maintains at each step (the invariant), then check initialization, termination, and edge cases. Tracing one example is testing, not proving. The invariant is what bridges one input to all of them.

What "prove your algorithm is correct" actually means in an interview

If you took a discrete math course, you spent weeks on induction proofs with formal notation. That isn't what an interviewer wants. They want what a senior engineer does in code review: read the loop, ask "what's true at each iteration?", and check whether that property forces the right answer.

The two are related. They share the invariant idea. But the academic version is a paper proof, and the interview version is a 90 second verbal walkthrough. Mixing them up is why most candidates either freeze or write something that looks like exam notation.

When the interviewer says "convince me this works," they want three things in order: the property your loop holds, evidence it holds at every step, and a check that the final state gives the right answer. Doing this clearly is rare, and noticeable when you can.

The two checks

Two checks carry the whole method.

1. State and verify the loop invariant. Before tracing any code, write down what's supposed to be true at the start of each iteration. Then trace 3 to 4 iterations, confirming the property after each one.
2. Check boundaries and termination. The invariant covers the loop body. Boundaries cover what happens before the loop starts, after it ends, and on degenerate inputs (empty array, single element, all identical values, maximum size).

Most candidates skip step 1 and jump straight into tracing a specific input. That's testing. Testing tells you it works for that input. The invariant tells you it works for every input.

The difference matters when an interviewer asks about an input you didn't trace. "My sliding window maintains the sum of exactly K elements at each step, and the update adds the new element and subtracts the leaving one" lets the interviewer check the mechanism. "I ran it on [2, 1, 5, 1, 3, 2] and got 9" leaves them wondering about everything else.

A worked example: fixed sliding window

Take the classic problem: given an array and a window size K, find the maximum sum of any contiguous subarray of length K.

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

Step 1: State and verify the invariant

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

Trace it on arr = [2, 1, 5, 1, 3, 2] with K = 3:

• Before the loop: window_sum = 2 + 1 + 5 = 8. The window covers indices 0..2. The invariant holds.
• i = 3: window_sum = 8 + arr[3] - arr[0] = 8 + 1 - 2 = 7. The window is now [1, 5, 1], and 1 + 5 + 1 = 7. Holds.
• i = 4: window_sum = 7 + arr[4] - arr[1] = 7 + 3 - 1 = 9. Window is [5, 1, 3], sums to 9. Holds.
• i = 5: window_sum = 9 + arr[5] - arr[2] = 9 + 2 - 5 = 6. Window is [1, 3, 2], sums to 6. Holds.

The reason the invariant is maintained matters more than the trace itself. The update adds the element entering the window and subtracts the one leaving. That's the mechanism, not just the result.

Step 2: Check boundaries and termination

Initialization: the code computes the sum of the first K elements directly, so the invariant holds before the loop runs.

Termination: the loop runs from K to len(arr) - 1, so the final window covers the last K elements. max_sum has tracked the maximum across every window the loop visited.

Edge cases:

• K == len(arr): the loop body never runs, and the initial window_sum is already the answer.
• All negative numbers: the invariant doesn't depend on sign, so it still holds.
• K == 1: each window is one element. The update shifts by one position correctly.

That's a complete interview-grade correctness argument. You stated what's true at every step, you explained why the update preserves it, and you confirmed the final state gives the right answer.

Where most candidates lose the argument

Five ways correctness reasoning falls apart, all avoidable:

• "It works on my example" fallacy. Tracing one input is a single data point. You haven't proven anything about the inputs you didn't trace. The invariant is what generalises.
• Not articulating the invariant. You probably have an intuitive sense of what each iteration does. Without putting that into a checkable sentence, the interviewer hears handwaving at the code, not a claim.
• Skipping boundary checks. The invariant covers the loop body. It doesn't tell you what happens on an empty array, a single element, or when K equals the array length. Each of those needs separate verification.
• Proving termination, not correctness. "The loop runs n times and exits" tells the interviewer the algorithm halts. It says nothing about whether the output is right. Termination and correctness are independent properties.
• Overcomplicating the argument. If your reasoning takes three paragraphs, your algorithm might be too complex. Simpler algorithms have simpler invariants. That's part of why interviewers prefer elegant solutions.

Invariants change shape across patterns

The sliding window invariant tracks one running variable. Other patterns produce invariants with different shapes, and recognising those shapes is half of what makes the skill transfer.

Pattern	Invariant shape
Sorted two pointers	The answer, if it exists, lies within [left, right]. Each step shrinks the search space without skipping a valid pair.
Binary search	The target, if present, lies within arr[low..high]. Every iteration halves the range while preserving that guarantee.
BFS on unweighted graph	When a node is dequeued, its recorded distance equals the shortest path from the source. This depends on FIFO ordering and equal edge weights.
Topological sort via DFS	A node is added to the result only after all its descendants have been added. Reversing the post-order produces a valid ordering.
0/1 knapsack DP	dp[i][w] equals the maximum value using items 0..i with capacity w. Each cell depends only on previously computed cells.

The two step structure is the same across all of them. State the property, verify the boundaries. What changes is what the invariant looks like and how many variables it tracks.

Practising under time pressure

Knowing the method and producing one in 45 minutes are different. The bottleneck isn't understanding what an invariant is. It's stating one quickly for an algorithm you just designed.

A drill that works: pick a problem you've already solved. Set a timer for 60 seconds. Try to state the loop invariant in one sentence. If you can't, that's a signal you solved the problem by pattern matching, not by understanding what made it work. Re-read the code and figure out what property the algorithm depends on.

Run that drill on five problems across five different patterns each week. After a month, two things change. First, articulating invariants becomes reflexive. Second, your debugging gets faster, because checking whether the invariant still holds at each step pinpoints the broken iteration faster than tracing the full execution.

A second drill is wrong invariant spotting. Take a correct algorithm. Write down an invariant that sounds plausible but is subtly wrong. Find the iteration where it breaks. This trains the gap between invariants that describe what the code does and invariants that guarantee correctness. Most interview mistakes live in that gap.

I keep watching this play out across engineers I see prep. The ones who can articulate invariants under pressure are usually the ones who solved fewer problems but understood each one more deeply. The ones who froze had solved more but couldn't say what made any single algorithm work.

If you want a worked walkthrough of why the variable sliding window update preserves the invariant before you ever solve a problem with it, the variable sliding window lesson walks through it step by step.

Two halves of the same skill

Correctness reasoning and mental dry running pair together. The dry run gives you the trace. The invariant gives you the claim to verify against the trace. Practising them apart leaves a hole that interview pressure exposes. Practising them together is what makes the reasoning hold up when the algorithm is one you just designed.

The same idea shows up in dynamic programming. When you derive a recurrence, 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 structure, just with a table-shaped invariant instead of a scalar one.

If you’ve ever frozen when an interviewer said “prove your algorithm works,” the missing piece usually isn’t more problems.

It’s learning to articulate the invariant.

I wrote a longer breakdown covering:

• nested loop invariants
• wrong invariant drills
• DP correctness reasoning
• and how to structure interview-grade proofs without formal notation

Which algorithm did you finally feel confident in only after you could state its invariant out loud?