awelgorithms

Shrink while the window is invalid

Updated

While the window is invalid, exclude a[L] and L += 1. Stop when it becomes valid, or when the window is empty (R < L).

What to focus on

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

one shrink

a = [4, 1, 9], L=0 R=2, sum=14, cap=10
  1. 14 > 10 invalid
  2. exclude 4, L=1, sum=10
  3. 10 ≤ 10 valid stop

Result: L=1 R=2 · sum 10

two shrinks

a = [4, 1, 9, 1], L=0 R=3, sum=15, cap=10
  1. 15 > 10 exclude 4 → 11
  2. 11 > 10 exclude 1 → 10
  3. 10 ≤ 10 stop

Result: L=2 R=3 · sum 10

already valid

a = [7], L=0 R=0, sum=7, cap=10
  1. 7 ≤ 10
  2. do not shrink

Result: L=0 R=0 · sum 7

Try it

Write 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.

All values are positive integers. Start with L ≤ R. cap is a positive integer.

practise it with Awel find your weak spots: free skill check

LeetCode problems that use this skill