State and invariants

A loop invariant is checked in three steps. Initialisation: it is true before the first iteration. Maintenance: if it is true before an iteration, it is still true after. Termination: when the loop ends, the invariant plus the exit condition give the result.

Kadane's algorithm is a clean example. Invariant: after index i, current is the best sum of a subarray ending exactly at i, and best is the best sum anywhere in arr[0..i]. Step through the animation and check that both statements hold at every frame.

1public static int maxSubarray(int[] arr) {
2    int current = arr[0], best = arr[0];          // current = best sum of a run ending at i
3    for (int i = 1; i < arr.length; i++) {
4        current = Math.max(arr[i], current + arr[i]);   // extend the run or restart at i
5        best = Math.max(best, current);
6    }
7    return best;
8}

Many algorithms keep a summary of what has been seen instead of re-scanning: a running sum, a frequency map, or the number of satisfied requirements. The invariant states exactly what the summary means, for example “count[v] is the number of times v occurs in the current window”.

Every operation that changes the underlying data must update the summary in the same step. Forgetting the update when the left edge of a window moves is the most common sliding-window bug.

1// invariant: count[c] = occurrences of c in s[left..right]
2int[] count = new int[128];
3int left = 0;
4for (int right = 0; right < s.length(); right++) {
5    count[s.charAt(right)]++;          // right edge moved: update the summary
6    while (count[s.charAt(right)] > 1) {
7        count[s.charAt(left)]--;       // left edge moves: update it too
8        left++;
9    }
10    // here: s[left..right] has no repeated characters
11}

For a sliding window, write down what holds after each outer iteration. In “minimum size subarray sum”: after shrinking, the window [left..right] has sum below the target, and every valid window ending at right has already been recorded.

That invariant justifies the while loop: it shrinks exactly until the window is no longer valid, so it never misses a shorter valid window and never stops early.

1public static int minSubArrayLen(int target, int[] arr) {   // all values positive
2    int left = 0, sum = 0, best = Integer.MAX_VALUE;
3    for (int right = 0; right < arr.length; right++) {
4        sum += arr[right];                          // grow the window
5        while (sum >= target) {                     // valid: try to shrink it
6            best = Math.min(best, right - left + 1);
7            sum -= arr[left++];
8        }
9    }
10    return best == Integer.MAX_VALUE ? 0 : best;
11}

Two-pointer algorithms are correct when every move discards only candidates that cannot be part of an answer. In two-sum on sorted data, if arr[lo] + arr[hi] < target, then arr[lo] plus any remaining value is also too small, so lo can be discarded permanently.

Write that argument for every pointer move. If you cannot, the algorithm may skip a valid answer, and a brute-force test will usually find the counterexample.

1public static int[] twoSum(int[] arr, int target) {     // arr is sorted
2    int lo = 0, hi = arr.length - 1;
3    while (lo < hi) {
4        int sum = arr[lo] + arr[hi];
5        if (sum == target) return new int[] { lo, hi };
6        if (sum < target) lo++;          // need a bigger sum
7        else hi--;                       // need a smaller sum
8    }
9    return new int[] { -1, -1 };
10}

Test pattern-based solutions against a brute-force reference. Generate many small random inputs, run both, and compare. Small inputs (n up to 8 or so) find most boundary bugs: empty windows, single elements, all-equal values and negative numbers.

Every animation on this site was checked this way. A useful habit is to deliberately break your solution once and confirm the test fails; a test that cannot fail checks nothing.

1Random rnd = new Random(42);
2for (int trial = 0; trial < 10_000; trial++) {
3    int[] arr = rnd.ints(rnd.nextInt(8) + 1, -5, 6).toArray();
4    int fast = maxSubarray(arr);                 // the O(n) solution under test
5    int slow = Integer.MIN_VALUE;                // brute force: every subarray
6    for (int i = 0; i < arr.length; i++) {
7        int sum = 0;
8        for (int j = i; j < arr.length; j++) { sum += arr[j]; slow = Math.max(slow, sum); }
9    }
10    if (fast != slow) throw new AssertionError(Arrays.toString(arr) + " " + fast + " vs " + slow);
11}