When the Interviewer Asks: “Why Does This Algorithm Work?”

You finish coding a binary search. The interviewer asks "why does this work?" You point at the code. They wait. The pointing isn't an argument, and the silence stretches.

This is the moment most candidates hit a wall, and it's the moment a small habit changes the room.

Key takeaways

• Algorithm correctness in interviews isn't a formal induction proof. It's a two step verbal argument.

• Step 1: state the loop invariant, the property that's true at the start of every iteration.

• Step 2: check initialization, termination, and edge cases (empty input, single element, max size).

• Tracing one example is testing, not proving. The invariant is what generalises one input to all of them.

• Different patterns produce different invariant shapes. The two step method stays the same.

Worth flagging: I built Codeintuition, a structured learning platform for coding interviews. This post walks through how to make correctness arguments concrete enough that an interviewer can check them in real time.

What interviewers want when they say "convince me"

The phrase "convince me your algorithm works" sounds like a formal request. It isn't. The interviewer wants what a senior engineer does in code review.

That review pattern is small and specific. Read the loop. Ask "what's true at each iteration?" Verify the property holds. Check the edges. Done.

The academic version is a paper proof with induction notation. The interview version is a 90 second walkthrough out loud. They share an idea, the loop invariant, but they live on different planets in execution.

When the interviewer asks the question, three things land in their ear: the property your loop holds, evidence it holds at every step, and a check that the final state gives the right answer. Most candidates produce zero of three.

The method, in two checks

Two checks, in this order:

Check one: state and verify the invariant. Before tracing any input, write down what's supposed to be true at the start of each iteration. Trace 3 to 4 iterations and confirm the property holds after each one. The reason it holds matters more than the trace itself.

Check two: check boundaries and termination. The invariant covers the loop body. It doesn't tell you what happens before the loop runs, after it ends, or on degenerate inputs. Empty array, single element, all identical values, maximum size. Each of those needs separate verification.

The reason check one gets skipped is straightforward: tracing a specific input feels like making progress. It isn't. Testing tells you it works for that input. The invariant tells you it works for every input. The interviewer is asking the second question.

Worked example: binary search

I'll use binary search instead of sliding window because the binary search invariant is one of the cleanest in algorithms, and the off by one mistakes are exactly where interview correctness arguments go wrong.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Step 1: state and verify the invariant

The invariant: the target, if present in the array, lies within arr[low..high] inclusive.

Trace it on arr = [1, 3, 5, 7, 9, 11] looking for 7:

• Initial state: low = 0, high = 5. The full array contains the target if it's anywhere. Invariant holds.

• Iteration 1: mid = 2, arr[2] = 5 < 7, so low = 3. The new range arr[3..5] = [7, 9, 11] still contains 7. Invariant holds.

• Iteration 2: mid = 4, arr[4] = 9 > 7, so high = 3. The new range arr[3..3] = [7] still contains 7. Invariant holds.

• Iteration 3: mid = 3, arr[3] = 7, return 3.

The reason the invariant is preserved matters more than the trace. When arr[mid] < target, every element in arr[low..mid] is also less than the target (sorted array), so the target cannot be there, and low = mid + 1 shrinks the range without dropping any candidate. The mirror argument holds for arr[mid] > target.

Step 2: boundaries and termination

Initialization: low = 0, high = len(arr) - 1 covers the entire array. The invariant holds before the loop runs.

Termination: each iteration strictly shrinks high - low + 1 by at least 1. The loop exits when low > high, meaning the range is empty and the target is not present.

Edge cases:

• Empty array: len(arr) - 1 = -1, so high < low from the start. Loop body never runs. Returns -1.

• Single element matching: low = high = 0, mid = 0. Returns 0.

• Single element not matching: one iteration adjusts low past high, returns -1.

• Target smaller than all elements: every iteration moves high down until high < low.

• Target larger than all elements: every iteration moves low up until low > high.

That's a complete correctness argument. State, mechanism, edges. The interviewer can check each piece against the code.

Where the argument falls apart in interviews

Five failure modes, each fixable with a habit:

1. The "it works on my example" trap. Tracing one input is one data point. The invariant is the bridge from one input to all of them. Without it, you're showing one successful trace.

2. No articulation of the property. You probably know what each iteration does. The interviewer doesn't, and the code alone doesn't say. Putting the property into a checkable sentence is the work.

3. Skipping the boundaries. The invariant covers the body. Edges need separate words. An empty array, a single element, an array of length equal to K. Each is a different question.

4. Termination versus correctness. "The loop runs n times and exits" tells the interviewer the algorithm halts. It says nothing about whether the output is right. Both are required, and they're independent.

5. Argument complexity. If your reasoning takes three paragraphs, the algorithm might be too complex. Simpler algorithms have shorter invariants. That's part of why interviewers prefer elegant solutions.

How invariant shape varies by pattern

The binary search invariant tracks a range. Other patterns track other things, and the shape tells you a lot about where the algorithm's bugs hide.

Sorted two pointers

Invariant: the answer pair, if it exists, lies within [left, right]. Each step shrinks the range without skipping any valid pair. The boundary check confirms that when left >= right, no pair remains.

Sliding window (fixed)

Invariant: at the start of each iteration, the running variable equals some property of the current window of K elements. The mechanism is the update. Add the element entering, subtract the one leaving. The trace confirms the update preserves the property.

BFS on unweighted graphs

Invariant: when a node is dequeued, its recorded distance equals the shortest path from the source. This depends on FIFO ordering and equal edge weights. Proving it requires showing no shorter path can exist for a dequeued node.

Topological sort via DFS

Invariant: a node enters the result only after all its descendants have entered. Reversing the post-order produces a valid ordering. The mechanism is the call stack returning in dependency order.

Dynamic programming

Invariant: dp[i] (or dp[i][j], depending on dimensions) equals the optimal answer for some sub-instance. Each cell depends only on previously computed cells. If base cases are correct and the recurrence preserves the definition, the final cell holds the global answer.

The two step structure stays constant. What changes is the shape of the invariant (scalar, range, table) and how many variables it tracks.

Practising the skill on its own

Knowing the method and producing one in 45 minutes are different problems. Three drills that build the muscle:

The 60 second invariant

Pick a problem you've already solved. Set a timer for 60 seconds. 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 makes it work. Re-read the code and find the property the algorithm depends on.

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 there.

Boundary-only review

Take a problem and skip straight to the edge cases without writing the full correctness argument. Empty input, single element, all identical values, maximum size. State what your algorithm does on each. This builds the habit of checking edges separately from the loop body.

Run any one of these drills on five problems across five different patterns each week. After a month, two things change. Articulating invariants becomes reflexive. Debugging gets faster, because checking whether the invariant still holds at each iteration pinpoints the broken step faster than tracing the full execution.

If you want a worked walkthrough of why the binary search range invariant survives the off by one updates, the binary search lesson walks through the mechanism step by step before you ever solve a problem with it.

The handoff to dynamic programming

When you derive a recurrence in DP, you're implicitly stating an invariant: dp[i] represents the optimal answer for the first i elements. Proving the recurrence correct uses the same two step process. If you've practised correctness reasoning on iterative algorithms first, the move to DP is much less of a jump than it usually feels.

The pattern across every algorithm class is the same. State what's true at each step. Verify the boundaries.

The shape of the invariant changes. The structure of the argument doesn't.

I originally posted this on my own blog, a slightly longer version with FAQs on multi-loop invariants and how to apply this when the algorithm has nested loops.

If you've ever been asked "convince me this works" and frozen, what was the first sentence you wished you'd had ready?