Shrink while the window is invalid03.04
While the window is invalid, exclude a[L] and L += 1. Stop when it becomes valid, or when the window is empty (R < L).
Window constraint: invalid while sum > cap. Shrink only. R is fixed. A one-cell [7] has sum 7 ≤ cap=10 so the loop does not run.
worked examples
Same skill, three traces. Read all three before you try it.
01one shrink - given
a = [4, 1, 9],L=0R=2,sum=14,cap=10- walk
14>10invalidexclude
4,L=1,sum=1010≤10valid stop- result
L=1R=2· sum10
02two shrinks - given
a = [4, 1, 9, 1],L=0R=3,sum=15,cap=10- walk
15>10exclude4→1111>10exclude1→1010≤10stop- result
L=2R=3· sum10
03already valid - given
a = [7],L=0R=0,sum=7,cap=10- walk
7≤10do not shrink
- result
L=0R=0· sum7
Write
Print (
On
shrinkWhileSumGt(a, cap).a is an array of positive integers. cap is the sum cap. L is the left index. R is the right index and stays fixed. Invalid means sum > cap. The window includes a[L..R] after each shrink.Print (
L, R) and sum when the loop stops. Return nothing.On
[4, 1, 9] from (0, 2) with cap=10; [4, 1, 9, 1] from (0, 3) with cap=10; [7] from (0, 0) with cap=10.constraintsAll values are positive integers. Start with L ≤ R. cap is a positive integer.
- Max Consecutive Ones III0/3 skills ready · sliding window · mediumopen
- Max Consecutive Ones III0/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.