Shrink to the smallest valid window
Updated
Once sum ≥ S, shrink while the window stays valid. Each successful exclude shortens a still-valid window. Stop when the next exclude would break S.
What to focus on
Window constraint: sum ≥ S with S=10 (or 7). Record the window before an exclude that would make sum < S. The last still-valid [L,R] is the smallest for this R.
Worked examples
tight to two cells
a = [4, 1, 9], S=10, L=0 R=2, sum=14- 14 ≥ 10, exclude 4 → 10 still valid
- 10 ≥ 10, exclude 1 → 9 invalid so do not keep that shrink
Result: smallest L=1 R=2 · [1, 9]
tight to [3,4]
a = [1, 2, 3, 4], S=7, L=0 R=3, sum=10- exclude 1 → 9 still ≥ 7
- exclude 2 → 7 still ≥ 7
- exclude 3 → 4 < 7 stop
Result: smallest L=2 R=3 · [3, 4]
already one cell
a = [7], S=7, L=0 R=0, sum=7- 7 ≥ 7
- exclude 7 → 0 empty, not ≥ 7
Result: smallest L=0 R=0 · [7]
Try it
Write minWindowSumAtLeast(a, S). a is an array of positive integers. S is the sum target. L is the left index. R is the current right index. The window includes a[L..R]. Valid means sum ≥ S. Return the smallest (L, R) for the final R. On [4, 1, 9] S=10; [1, 2, 3, 4] S=7; [7] S=7.
All values are positive integers. S is reachable at the current R.