Variable sliding window

When to use it

Use it when you want the longest or shortest stretch of neighbors that keeps a rule, and the length is not given: the rule decides when the window grows and shrinks.

It belongs to the search & scan group: Move one or two positions across the input so that nothing is looked at more than a few times.

Watch it work

A trail is split into stages, and the list gives the hours each stage takes. You may start at any stage and must walk the stages in order, skipping none. Return the largest number of stages you can walk in one day of 9 hours.

Input
hours = [2, 5, 6, 1, 2]
limit = 9

Output
3

The method

1. Start with an empty window: left at 0 and a total of 0
2. Take the next stage into the window on the right
3. While the total is over the limit, drop the leftmost stage
4. The window fits: keep its length if it is the longest
5. Every stage came in once: return the longest length

The run, one moment at a time

1. Step 1. The window is empty: left is at stage 0, the total is 0 and the best length is 0.

   hours: 2 5 6 1 2  (left at 0)
   total: 0
   best: 0
   

2. Step 2. Stage 0 comes in with 2 hours. The total is 2.

   hours: 2 5 6 1 2  (both at 0)
   total: 2
   best: 0
   

3. Step 4. 2 is within the limit of 9. The window is 1 stage long, longer than the best, 0. The best becomes 1.

   hours: 2 5 6 1 2  (both at 0)
   total: 2
   best: 1
   

4. Step 2. Stage 1 comes in with 5 hours. The total is 7.

   hours: 2 5 6 1 2  (left at 0, right at 1)
   total: 7
   best: 1
   

5. Step 4. 7 is within the limit of 9. The window is 2 stages long, longer than the best, 1. The best becomes 2.

   hours: 2 5 6 1 2  (left at 0, right at 1)
   total: 7
   best: 2
   

6. Step 2. Stage 2 comes in with 6 hours. The total is 13.

   hours: 2 5 6 1 2  (left at 0, right at 2)
   total: 13
   best: 2
   

7. Step 3. 13 is over 9. Drop stage 0 on the left: 13 - 2 = 11. Left moves to stage 1.

   hours: 2 5 6 1 2  (left at 1, right at 2)
   total: 11
   best: 2
   

8. Step 3. 11 is still over 9. Drop stage 1 on the left: 11 - 5 = 6. Left moves to stage 2. The window fits again, but 1 stage is not longer than the best.

   hours: 2 5 6 1 2  (both at 2)
   total: 6
   best: 2
   

9. Step 2. Stage 3 comes in with 1 hour. The total is 7. That fits, but 2 stages is not longer than the best, so nothing changes.

   hours: 2 5 6 1 2  (left at 2, right at 3)
   total: 7
   best: 2
   

10. Step 2. Stage 4 comes in with 2 hours. The total is 9.

    hours: 2 5 6 1 2  (left at 2, right at 4)
    total: 9
    best: 2
    

11. Step 4. 9 is within the limit of 9. The window is 3 stages long, longer than the best, 2. The best becomes 3.

    hours: 2 5 6 1 2  (left at 2, right at 4)
    total: 9
    best: 3
    

12. Step 5. Every stage came in once and went out at most once. The longest walk in one day is 3 stages: stages 2 to 4.

    hours: 2 5 6 1 2  (left at 2, right at 4)
    total: 9
    best: 3
    

The code

The numbered comments are the steps of the method.

function solve(hours, limit) {
  // 1. Start with an empty window: left at 0 and a total of 0
  let left = 0;
  let total = 0;
  let best = 0;
  for (let right = 0; right < hours.length; right++) {
    // 2. Take the next stage into the window on the right
    total += hours[right];
    // 3. While the total is over the limit, drop the leftmost stage
    while (total > limit) {
      total -= hours[left];
      left += 1;
    }
    // 4. The window fits: keep its length if it is the longest
    if (right - left + 1 > best) best = right - left + 1;
  }
  // 5. Every stage came in once: return the longest length
  return best;
}

def solve(hours, limit):
    # 1. Start with an empty window: left at 0 and a total of 0
    left = 0
    total = 0
    best = 0
    for right in range(len(hours)):
        # 2. Take the next stage into the window on the right
        total += hours[right]
        # 3. While the total is over the limit, drop the leftmost stage
        while total > limit:
            total -= hours[left]
            left += 1
        # 4. The window fits: keep its length if it is the longest
        if right - left + 1 > best:
            best = right - left + 1
    # 5. Every stage came in once: return the longest length
    return best

How to spot it

Asked: The longest run of neighboring items in which a rule holds

Take items in on the right while the rule holds. When it breaks, dropping items on the left repairs it, so you never start over.

Asked: The shortest run of neighboring items that reaches a goal

Grow on the right until the goal is reached, then drop items on the left while it still is. Each drop gives a shorter candidate.

Given: A substring or subarray, and its length is not given

Neighbors in order are what lies between two edges, and a rule must set the length. A subsequence, which may skip items, is not a window.

Limits: Up to 100,000 items, so trying every stretch is too slow

There are about 5 billion stretches. Two edges that only move forward make at most 200,000 moves between them.

Looks like it, but is not

• The stretch must be exactly k items long. Use Fixed-size sliding window. With the length given there is nothing to decide. One item comes in and one goes out at every move.
• You need the largest or smallest value inside the window at every position. Use Monotonic queue. One running number cannot follow a largest value: when it leaves, the next largest must be known. The queue keeps those candidates.
• You want the longest piece of a string that reads the same forward and backward. Use Expand around a center. Dropping letters on the left does not repair a piece that fails to mirror. Such a piece is grown from its middle outward.

Cost and mistakes

Time grows with the number of items, written O(n): each item comes in once on the right and goes out at most once on the left. Extra space is what you keep about the window: one total here, written O(1).

Watch out

• Shrink with while, not if. One new item can put the window so far over the limit that several items must go before it fits again.
• Dropping an item must always move the window toward the rule. With negative numbers a total can grow when an item leaves, and this method then gives wrong answers.

In the 150

4 problems of the 150 use it. Naming them gives their method away, so the list is folded.