What property must a window's validity predicate have for the grow-right/shrink-left technique to be correct?

## The question behind the pattern The grow-right/shrink-left window makes a strong commitment: neither pointer ever moves backward, and window starts that have been abandoned are never reconsidered. That commitment is only sound if the *predicate* — the rule deciding whether a window is "valid" or "qualifying" — has a structural property that makes reconsideration provably pointless. The property is **monotonicity under window inclusion**, and it comes in two mirrored directions matching the two goal directions. ## The two directions, precisely **Longest valid window** (predicates like "at most k distinct values", "sum at most a cap over non-negative values"): validity must be **closed under shrinking** — every sub-window of a valid window is valid. Equivalent contrapositive: if a window is invalid, every extension of it is invalid. This gives the shrink loop its guarantee: once `[left..right]` is invalid, growing it cannot help, and shrinking must eventually restore validity (in the worst case, at the empty window). It also means the valid left positions for a fixed `right` form a contiguous suffix — so the loop, stopping at the first valid `left`, has found the longest valid window ending at `right`, and everything to its left is proven useless forever. **Shortest qualifying window** (predicates like "contains every required keyword"): qualification must be **closed under growth** — every super-window of a qualifying window qualifies. Then for a fixed `right`, the qualifying left positions form a contiguous prefix, and shrink-while-valid walks to its boundary: the tightest qualifying window ending at `right`. In both cases the pointer sweep is really a boundary-tracking argument: monotonicity makes "valid" and "invalid" separate cleanly at one frontier per right edge, and the two pointers track that frontier as it moves — only ever forward. ## A predicate that breaks it Take "the window sums to exactly S", with values that may be negative. Consider the sequence `3, -1, 2` and `S = 4`: - `[3]` sums to 3 — not valid. - `[3, -1]` sums to 2 — not valid. - `[3, -1, 2]` sums to 4 — valid. - `[-1, 2]` sums to 1; `[2]` sums to 2 — not valid. Validity here is closed under neither shrinking nor growth: extending a window can move the sum toward *or* away from S, and so can shrinking, because removing a negative element *raises* the sum. Valid windows are scattered arbitrarily rather than forming a frontier. Any forward-only pointer rule — "shrink when the sum exceeds S", say — makes a locally plausible move that discards starts which would have been needed later. The failure mode is the dangerous kind: the code runs to completion, touches every element, looks linear and elegant, and returns a wrong answer on inputs the happy-path tests never contained. Restrict the same predicate to strictly positive values and monotonicity returns: the sum strictly rises with every admission and strictly falls with every eviction, so "sum exceeds S → shrink" is sound again. The predicate alone does not decide applicability — the predicate *plus the data's guarantees* does, which is why the senior move is to ask about value ranges before choosing the technique. ## When the check fails, reformulate Non-monotone predicates usually yield to a different tool rather than a patched window. Exact-sum-with-negatives is solved by prefix sums with a hash map of previously seen prefix values — a window `(i..j]` sums to S exactly when `prefix[j] - prefix[i] = S`, so one pass probing for `prefix[j] - S` finds all solutions in O(n) expected time. The general lesson: the window pattern is not defined by "contiguous subarray problem" but by "contiguous subarray problem *with a monotone predicate*", and recognizing the second half is what separates applying a pattern from pattern-matching on surface features. ## The interview-room test Before committing, ask the monotonicity question out loud in whichever direction the goal requires: *"If this window violates the constraint, does every extension of it also violate?"* (longest goals), or *"If this window qualifies, does every extension still qualify?"* (shortest goals). If the answer is no — most often because elements can cancel, as negatives cancel positives — say so, name the counterexample, and pivot. Demonstrating the check is worth more than a memorized solution, because it shows you know *why* the pattern works, not merely *that* it usually does.