CodeWithYash

Intermediate · Module 7 · Lesson 5

When windows fail

Negative values and non-monotonic constraints.

15–25 min readLesson 41 of 123

Lesson 41 of 123

1d streak

Theory lesson · Step-by-step

Understand When windows fail

Negative values and non-monotonic constraints.

Worked approach

Trace the reasoning step by step

  1. 1Define the window condition and maintained aggregate for When windows fail.
  2. 2Expand the right boundary and add the incoming value.
  3. 3Shrink from the left while the condition requires it, removing outgoing values.
  4. 4Record the answer only when the current window satisfies the requested condition.
  5. 5Verify whether negative values or non-monotonic conditions invalidate the window strategy.

Concrete example

Why does shrinking by sum fail on [2,-5,10]?

  1. 1Adding -5 lowers the sum.
  2. 2Removing 2 also lowers it, but future 10 changes feasibility non-monotonically.

Use prefix states or another method when boundary movement is not monotonic.

What must remain true (Loop Invariant)

The active window in When windows fail contains exactly the elements between its boundaries, and its stored aggregate matches that range.

Cost Model

Complexity & Trade-offs

Alternative prefix-state method
Problem-dependent
Problem-dependent
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Contiguous subarrays or substrings with incrementally maintainable state.
  • Longest, shortest, count, sum, or frequency constraints.
  • Streaming range calculations.

Common mistakes

  • Using a variable window when feasibility is not monotonic under shrinking.
  • Adding an incoming item but forgetting to remove the outgoing one.
  • Updating the answer before the window is valid.

Practice prompts

  • Reproduce the worked When windows fail example without looking at the trace.
  • Change one input condition and explain whether the When windows fail invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.