Shrink to the smallest valid window03.05
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.
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
Same skill, three traces. Read all three before you try it.
01tight to two cells - given
a = [4, 1, 9],S=10,L=0R=2,sum=14- walk
14≥10, exclude4→10still valid10≥10, exclude1→9invalid so do not keep that shrink- result
- smallest
L=1R=2·[1, 9]
02tight to [3,4] - given
a = [1, 2, 3, 4],S=7,L=0R=3,sum=10- walk
exclude
1→9still ≥7exclude
2→7still ≥7exclude
3→4<7stop- result
- smallest
L=2R=3·[3, 4]
03already one cell - given
a = [7],S=7,L=0R=0,sum=7- walk
7≥7exclude
7→0empty, not ≥7- result
- smallest
L=0R=0·[7]
Write
Return the smallest (
On
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.constraintsAll values are positive integers. S is reachable at the current R.
- Minimum Size Subarray Sum0/3 skills ready · sliding window · mediumopen
- Minimum Size Subarray Sum0/3 skills ready · sliding window · mediumopen
Every Check with Awel is frozen here. Open one to read the code or load it back into the editor.