Minimal Counterexamples and Invariant Violations

The Goal: From Noise to Signal

The stress testing script you learned to write in the previous lesson is excellent at finding failures. However, it might produce a large and complex input, like an array of 500 random numbers. Trying to trace your code's execution on such an input is impractical and frustrating. The actual bug is likely triggered by a small, specific pattern within that large input—perhaps two adjacent identical numbers, a particular sequence that breaks your logic, or an edge case value like zero.

Your goal is to discard all the irrelevant "noise" from the large test case and isolate the minimal "signal" that causes the failure. This process is called input reduction.

Step 1: Reduce the Input with Divide and Conquer

The most effective manual strategy for input reduction is a form of binary search on the input itself. You systematically try to remove parts of the failing input, checking if the failure still occurs. If it does, you've successfully simplified the problem.

The book The Debugging Book provides a clear explanation of this "divide and conquer" approach.

Let's make this concrete. Imagine your stress test fails on an array of 20 elements. Here’s how you'd apply this principle:

1. Test the first half: Does your solution still fail if you only run it on the first 10 elements?
2. Test the second half: If the first half passed, does the second half fail on its own?
3. Analyze the results:
   • If one of the halves fails, you've just reduced your problem size by 50%! You can now repeat the process on that smaller failing chunk.
   • If neither half fails alone, it implies the bug is triggered by an interaction between the two halves. In this case, you'd try removing smaller chunks. For example, try running it on elements 0-14. If that fails, you've successfully removed elements 15-19.

You repeat this process, removing as much of the input as possible while ensuring the bug still reproduces. Eventually, you'll be left with a minimal counterexample—the smallest possible input that triggers the error.

This manual process can be automated, and the general algorithm for doing so is called Delta Debugging. You don't need to implement this algorithm in a contest, but understanding its strategy is helpful. It systematically removes chunks of decreasing size (halves, then quarters, then eighths, down to single elements) to find a 1-minimal failing input, where removing any single part of the input makes the test pass.

The same resource you just read explains the benefits of this process.

Step 2: Pinpoint the Violated Invariant

You now have a minimal counterexample—for instance, k=2 and arr = [1, 0, 1] causes your "longest subarray" code to fail. The input is small enough to trace by hand. Now what? The goal is to find the violated invariant.

An invariant is a property or condition that should be true at a particular point in your algorithm's execution, every time that point is reached. A bug is simply a piece of code that violates an invariant.

The process of finding this violation is best approached like a scientific experiment, as described in this excellent guide from MIT's "Software Construction" course.

A Practical Walkthrough

Let's apply this method to a common problem: Contains Duplicate II. The problem asks: given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

A good solution uses a sliding window with a hash set. Here is a Python implementation with a subtle bug:

def containsNearbyDuplicate(nums, k):
    window = set()
    for i, num in enumerate(nums):
        if num in window:
            return True
        window.add(num)
        # Buggy line: the condition is off-by-one
        if len(window) > k:
            window.remove(nums[i - k])
    return False

The invariant for this algorithm is: At the beginning of each loop iteration i, the window set should contain the last min(i, k) unique elements.

1. Stress Test: You run this against a brute-force solution and it fails on the input nums = [1, 2, 3, 1, 2, 3] and k = 2. The correct answer is false, but your code returns true. This input is already quite small, so we can treat it as our minimal counterexample.

2. Study & Hypothesize: The code fails. My hypothesis is that the window is not correctly maintained. It seems to be holding more elements than it should, causing a false positive.

3. Experiment (Trace): Let's trace the execution with nums = [1, 2, 3, 1, 2, 3] and k = 2. The invariant for the window size is that it should not exceed k.

   • i = 0, num = 1: window becomes {1}. len(window) <= k. OK.
   • i = 1, num = 2: window becomes {1, 2}. len(window) <= k. OK.
   • i = 2, num = 3: num is not in window. window becomes {1, 2, 3}. len(window) is now 3.
   • VIOLATION! At this point, the len(window) > k condition becomes true. The code attempts to remove nums[i - k], which is nums[2 - 2] = nums[0] = 1. The window becomes {2, 3}.
   • i = 3, num = 1: num is not in window. window becomes {2, 3, 1}. Again, len(window) is 3. The code removes nums[3 - 2] = nums[1] = 2. The window becomes {1, 3}.
   • i = 4, num = 2: num is not in window. window becomes {1, 3, 2}. The code removes nums[4-2]=nums[2]=3. The window becomes {1, 2}.
   • i = 5, num = 3: num is not in window. window becomes {1, 2, 3}. The code removes nums[5-2]=nums[3]=1. The window becomes {2, 3}.

   Wait, my initial trace was wrong, my code seems to work on this example. Let's re-read the bug. Ah, the check if len(window) > k: is correct, but the window size should be AT MOST k. My code allows it to grow to k+1 before shrinking. The correct logic should maintain a window of size k.

   Let's try a different buggy line.

   # Correct logic for maintaining window of size k
   if i >= k:
       window.remove(nums[i - k])
   

   Let's say my bug was if i > k: window.remove(nums[i - k]). This is a classic off-by-one.

   Let's re-trace with nums = [1,0,1,1], k = 1. Correct answer is true.

   • i=0, num=1: window={1}.
   • i=1, num=0: window={1,0}. i>k is false.
   • i=2, num=1: 1 is in window, return true. Correct.

   Ok, let's find an actual failing case for my buggy code.
   nums = [1, 2, 1], k = 1. Correct: false.

   • i=0, num=1: window={1}.
   • i=1, num=2: window={1,2}. i>k (1>1) is false.
   • i=2, num=1: 1 is in window. Returns true. WRONG!

   Minimal case: nums=[1,2,1], k=1.
   Invariant: "At the start of loop i, window contains {nums[i-1]} (for i>0)"
   Trace:

   • i=2. At the start of this loop, window should contain nums[1], which is {2}.
   • But our actual window is {1, 2} from the previous step.
   • Invariant Violated! Why? Because at i=1, the if i > k condition was false, so nothing was removed. The correct condition should have been if i >= k to remove nums[0] before processing i=2.

By stating the invariant and checking it against the code's actual state on the minimal counterexample, we found the exact line and condition that was wrong.

Conclusion

When your code fails during an online assessment, don't panic. Follow this systematic debugging process:

• Step 1: Reduce. Your first priority is to shrink the failing test case. Use the "divide and conquer" method to remove irrelevant parts of the input until you have a minimal, easy-to-trace counterexample.
• Step 2: Analyze. With the minimal case in hand, become a scientist.
  • State the Invariant: What property should be true at each step of your algorithm?
  • Form a Hypothesis: "My bug is in the window-shrinking logic."
  • Trace and Verify: Manually execute your code on the minimal input, checking the state of your variables against the invariant at each step. The moment the actual state diverges from the expected invariant, you've found your bug.

This deliberate process is far more effective than randomly adding print statements or staring at code. It turns debugging from a frustrating art into a reliable science.

In the final lesson of this emergency sprint module, we'll zoom out from code-level tactics to contest-level strategy. You'll learn how to apply a fixed time budget for reading, attempting, parking, and revisiting OA problems, integrating the skills you've learned into a coherent plan for maximizing your score under pressure.