Tracing Java Algorithms: Invariants and Off-by-One Errors

Hello. In the previous lesson, you designed boundary, invalid, and adversarial tests from an algorithm’s contract. Those tests tell you that a solution fails. Manual tracing now gives you a disciplined way to determine where and why it fails—especially when a loop skips the last item, reaches one item too far, or lets its internal state become inconsistent.

This is the final hands-on debugging skill in the Coding Interview Foundations module. By the end, you should be able to trace a Java loop at meaningful checkpoints, state its invariant, and distinguish an off-by-one boundary error from an invariant-maintenance error.

---

Trace the program as Java executes it

A manual trace is a small, deliberate simulation of execution. You choose a compact input, record the changing values of variables, evaluate each condition with the current state, and compare that state with what the algorithm claims should be true.

The important idea is that tracing is not merely “running code on paper.” It is a way to check three connected claims:

1. Safety: Does the code access only valid indices and references?
2. Correctness: Does its state still represent the work completed so far?
3. Completion: When the loop stops, has it processed everything required?

An off-by-one error occurs when a loop, range, or index is short by one item or extends one item too far. Arrays make this especially visible because an array with length $n$ has valid indices from $0$ through $n-1$. The value array.length is a valid boundary position, but never a valid array index.

A Java for loop such as this:

for (int i = 0; i < nums.length; i++) {
    process(nums[i]);
}

has a precise execution rhythm:

1. int i = 0 runs once.
2. Java evaluates i < nums.length.
3. If it is true, Java runs the body, including process(nums[i]).
4. Java runs i++.
5. Java returns to the condition.

When i becomes nums.length, the condition is false. That final false check is useful information: it tells us that every valid index was considered exactly once.

---

Invariants: the meaning of the variables at a checkpoint

A loop invariant is a statement that must be true every time the loop condition is evaluated: before the first iteration, after every completed iteration, and when the loop exits.

For a left-to-right scan, it is useful to describe the prefix already processed with half-open range notation:

• a[0..i) means elements at indices $0$ through $i-1$.
• The endpoint i is excluded.
• When i is 0, the range is empty.
• When i is a.length, the range is the entire array.

This convention matches Java’s indexing model particularly well: i means the next index to inspect, not the last index inspected.

Consider a method that counts occurrences of a value:

static int frequencyOf(int key, int[] a) {
    int i = 0;
    int count = 0;

    while (i < a.length) {
        if (a[i] == key) {
            count++;
        }
        i++;
    }

    return count;
}

At each evaluation of i < a.length, its invariant is:

i is the next unprocessed index; count equals the number of occurrences of key in the already processed range a[0..i).

There is also an index-bound fact:

0 <= i && i <= a.length.

That final <= is intentional. At a loop checkpoint, i == a.length is valid: it means no elements remain to process. But the loop body may only access a[i] when i < a.length.

A robust trace therefore checks four questions:

Check	What you verify	Typical defect revealed
Initialization	Is the invariant true before the first guard check?	Wrong starting index or accumulator value
Maintenance	Does one iteration restore the invariant?	Missing update, wrong update, wrong order
Progress	Does some boundary move toward termination?	Infinite loop or repeated processing
Termination	When the guard is false, does the invariant imply the required result?	Last item skipped or incorrect return state

This is stronger than memorizing whether a loop should use < or <=. The correct operator follows from what i means.

---

Build a trace table around state changes

A trace table makes variable state visible. Include only the variables needed to understand the method: loop counters, pointers, accumulators, relevant conditions, and return values. For array code, record the input separately rather than copying it into every row unless the algorithm mutates it.

Trace the correct frequencyOf method with:

a = new int[] {5, 2, 5};
key = 5;

Record the state at each guard checkpoint, immediately before while (i < a.length) is evaluated:

Checkpoint	i	Processed range	count	Guard i < a.length	Invariant check
Initial state	0	a[0..0)	0	true	Empty prefix contains zero 5s
After processing index 0	1	a[0..1) = {5}	1	true	Prefix contains one 5
After processing index 1	2	a[0..2) = {5, 2}	1	true	Prefix still contains one 5
After processing index 2	3	a[0..3) = entire array	2	false	Entire array contains two 5s

At termination, the invariant says count is the number of matches in a[0..i). The false guard says i is a.length. Substitute that into the invariant: count is now the number of matches in the whole array. Returning it is correct.

Two habits make this trace reliable:

• Evaluate a[i] == key using the value of i at the start of that iteration.
• Apply i++ only after the body. The next checkpoint reflects the new i.

Do not require the invariant to be true after every individual line. During an iteration, the algorithm may temporarily change count before changing i. What matters is that the invariant is restored before Java evaluates the loop guard again.

---

Diagnose three common failures

1. The loop runs one iteration too far

Suppose a candidate changes the guard:

while (i <= a.length) {
    if (a[i] == key) {
        count++;
    }
    i++;
}

The first three iterations seem normal on {5, 2, 5}. The revealing checkpoint is the fourth guard evaluation:

Checkpoint	i	count	Guard i <= a.length	Consequence
After processing index 2	3	2	true	Body attempts a[3]
Array length	3	—	—	Valid indices end at 2

This is an off-by-one overshoot. Notice a subtle but important point: at i == a.length, the counting invariant still holds. The failure is that the guard incorrectly permits entry into a body that reads a[i].

A clear interview explanation is:

“i == a.length is the valid completed state, not a valid element position. The body reads a[i], so the guard must establish i < a.length before that access.”

2. The loop stops one iteration too early

Now consider the opposite error:

while (i < a.length - 1) {
    if (a[i] == key) {
        count++;
    }
    i++;
}

Use an input where the final item matters:

a = new int[] {8, 4, 8};
key = 8;

The loop processes indices 0 and 1. At i == 2, the condition 2 < 2 is false, so it exits and returns 1.

The result should be 2, because the last element was never inspected. This time the code does not crash; it simply violates the method’s contract.

The diagnosis is:

“On exit, i equals a.length - 1, so the invariant only describes the prefix before the final element. A false guard no longer proves that the whole array has been processed.”

This is an off-by-one undershoot. A test case with a match only at the final index, like the one above, is designed specifically to expose it.

3. The invariant is not maintained

Finally, look at a different kind of error:

while (i < a.length) {
    if (a[i] == key) {
        count++;
    }
    // i++ is missing
}

Use the smallest revealing input:

a = new int[] {5};
key = 5;

Checkpoint	i	Processed range according to i	count	Invariant true?
Initial	0	Empty	0	Yes
After first body execution	0	Still empty	1	No

count now says one matching element has been processed, but i == 0 says the processed range is still empty. The invariant has been violated.

The defect also prevents progress: i never changes, so the guard remains true forever. On this particular input, count will continue increasing while the algorithm repeatedly reprocesses index 0.

This is not primarily an off-by-one error. It is an invariant-maintenance and progress failure.

---

A repeatable debugging routine

When handed a Java loop in an interview, code review, or debugging task, use this compact routine.

1. State the role of each variable.
   Say whether i is the next unprocessed index, the last processed index, a window boundary, or something else. Do not infer its meaning from the variable name alone.

2. Write the intended invariant in plain language.
   For example: “Before each guard check, count is the number of matches in the prefix before i.”

3. Choose a minimal revealing input.

   • To catch a skipped final element, put the decisive value at the last index.
   • To catch an overrun, use a short array so the invalid index is obvious.
   • To catch a state violation, choose input that takes the suspicious branch.

4. Trace guard checkpoints.
   Record the state before the first condition, after each completed body, and at the final false condition.

5. Classify the first failure precisely.

   • A body access with i == a.length is a safety/off-by-one overshoot.
   • A false guard before all required items are processed is an off-by-one undershoot.
   • State that no longer matches the processed range is an invariant violation.
   • A boundary that does not move toward exit is a progress failure.

This vocabulary matters in interviews. Rather than saying, “There’s probably an edge case,” you can explain the exact break:

“The invariant holds initially, but after this branch count describes one more item than i says has been processed. The update fails to restore the invariant before the next guard evaluation.”

That is a concise correctness argument, not just a guess based on output.

---

Key takeaways

Manual tracing connects test failures to the exact loop logic responsible:

• Trace current state, especially at each loop-guard checkpoint.
• Define what an index means: “next unprocessed” and “last processed” lead to different valid guards.
• Use a loop invariant to connect variables to the part of the input already handled.
• Check initialization, maintenance, progress, and termination separately.
• i == array.length is a valid completion boundary but an invalid array index.
• A loop can preserve its invariant yet still have a wrong guard; the exit condition must imply the method’s postcondition.
• Use short, adversarial inputs that force the first index, final index, and suspicious branch to matter.

Next, you will practice explaining a completed Java solution clearly while responding to interviewer prompts—connecting the problem contract, algorithm choice, complexity, correctness argument, and targeted tests into one coherent narrative.