Largest Gap Between Readings

The Bug Report

The program is meant to read a list of sensor readings and print the largest jump between two readings that sit next to each other in the list — the biggest absolute difference between any reading and the one immediately after it. It runs, it prints a number, and on plenty of inputs that number is right. On this one it is not.

Input that shows the problem

5
3 9 4 4 12

What the program prints

6

What it should print

8

The readings are 3 9 4 4 12, so the neighbouring gaps are 6, 5, 0 and 8, and the largest is 8. The program reports 6 instead — which happens to be the first gap in the list. Looking across other inputs, the pattern is that the answer is only ever wrong when the biggest jump happens to sit near the end.

Input Format

The input has exactly two lines:

• Line 1: a single integer n, the number of readings (at least 2).
• Line 2: n integers separated by single spaces, the readings themselves, in the order they were recorded.

Output Format

Print one line containing a single integer: the largest absolute difference between two readings that are next to each other in the list.

How to Debug It

Start by making the failure as small as you can, because a loop with one pair to check is much easier to reason about than one with four. The smallest input the constraints allow is two readings with one gap, so try 2 followed by 1 5. The correct answer is obviously 4. If what comes back is 0, you have learned something valuable without reading a single line of the loop: on the smallest legal input, the loop does not measure anything at all.

Now make the program tell you what it is doing rather than guessing. Put a print inside the loop that shows i and the gap measured on that pass, and run the failing five-reading input again. You will get a short list of visited positions. Separately, write out by hand every neighbouring pair 3 9, 9 4, 4 4, 4 12 — that is four pairs for five readings. Compare the two lists side by side and count.

That comparison gives you a hypothesis you can state in one sentence, about how many pairs the loop visits versus how many pairs exist. Test it by changing exactly one thing: the bound the loop counts up to. Nothing else in the function needs to move. Re-run both the two-reading input and the five-reading input, then re-run the second sample — the one that was already passing — to make sure your change did not break the case that worked. A fix that repairs one input and breaks another is not a fix.

What Was Wrong

The loop was written as for i in range(len(readings) - 2). The reasoning behind that is easy to reconstruct and completely understandable: the last valid index in a list of length n is n - 1, and the last pair starts at index n - 2, so it looks as though the loop should count up to n - 2.

The mistake is that range(stop) never includes stop itself — range(4) gives 0, 1, 2, 3. So range(len(readings) - 2) visits indices 0 through n - 3, and the pair starting at index n - 2 (the last pair in the list) is skipped every single time. The subtraction of one that range already performs for you was performed a second time by hand.

The fix is to count the pairs rather than the indices. A list of n readings has n - 1 neighbouring pairs, starting at indices 0 through n - 2, which is exactly range(len(readings) - 1):

for i in range(len(readings) - 1):

That one character also repairs the two-reading case: range(1) runs the body once, measuring the single pair that exists, instead of range(0) running it zero times and leaving the initial 0 in place.

Common Mistakes

• Fixing it by widening the loop to range(len(readings)). That does visit the final pair, but on the last pass readings[i + 1] reaches one position past the end of the list and the program crashes with an IndexError instead of printing a wrong answer. When a loop reads i + 1, the loop has to stop one position earlier than the list ends, not at the same place.
• Patching the symptom by measuring the last pair separately after the loop. It produces the right number on this input, but it leaves the real off-by-one in place and adds a second copy of the gap calculation that can drift out of step with the first. One correct bound is easier to trust than two calculations that have to agree.
• Leaving largest = 0 as the starting value without checking whether it is safe. Here it is safe, because gaps are absolute differences and so never negative, and because at least one pair is guaranteed. It is worth confirming that rather than assuming it: a starting value of 0 in a problem where the answer could legitimately be negative is exactly how a bug like this one hides.