Expand first then shrink
Updated
For each R, add a[R] first. Only after the window is valid (sum ≥ S) do you shrink L. Do not shrink first — the window may not yet be valid.
What to focus on
Window constraint: shortest window with sum ≥ S, S=10. Order is expand → (maybe) shrink, not the reverse. Shrink on an unmet window cannot create the missing sum.
Worked examples
expand to 14 then shrink
a = [4, 1, 9], S=10- R=0 sum=4
- R=1 sum=5
- R=2 sum=14 then shrink to [1,9] sum=10
Result: valid after expand, tight after shrink
need the last cell
a = [1, 2, 3, 4], S=10- R=0..2 sums 1,3,6 all < 10
- R=3 sum=10, then shrink while ≥ 10
Result: do not shrink before R=3
shrink-first fails
a = [4, 1, 9], S=10, L=0 R=0- sum=4 < 10
- shrinking to empty loses 4 and still unmet
Result: expand first
Try it
Write expandThenShrink(a, S). a is an array of positive integers. S is the sum target. For each R, include a[R] first. Shrink L only after sum ≥ S. The window includes a[L..R]. Print the order of moves. Show why shrink-first on (0, 0) fails. Return nothing. On [4, 1, 9] S=10; [1, 2, 3, 4] S=10.
All values are positive integers. S is reachable from some prefix.