Training Material

## Sliding Window Algorithms

Along one side of a road there is a sequence of vacant plots of land. Each plot has a different area (non-zero). So, the areas form a sequence A, A, … A[N].

You want to buy K acres of land to build a house. You want to find a segment of continguous plots (i.e., a subsection in the sequence) of minimum length whose sum is exactly K.

Solution

First attempt

Compute prefix sums. For each (i,j) check if A[j] - A[i] = K. Among all such sections, choose the one where j - i is minimized.

This takes time N2. Can we do better?

The prefix sums form a sequence of values in ascending value:
P < P < … < P[N]

For each i, we want to find a j such that P[j] - P[i] = K. Since the prefix sums are sorted in ascending order, we can find the j for each i using binary search, instead of exhaustively scanning P[i+1], … P[N].

This improves the complexity to N log N.

Can we do it in time proportional to N?

For each i, compute if there is a segment starting at i that adds up to exactly K.

Start at A. Add A, A, …

• If we reach A[j] such that sum till A[j] is exactly K, note this down.
• If the sum till A[j-1] is less than K and the sum till A[j] exceeds K, there is no solution starting from A.
• At this point, we subtract A from the sum. We automatically have the sum starting from A upto A[j].
• The sum from A upto A[j-1] must be less than K (since the sum from A to A[j-1] was less than K). If there is already a solution for A, it must be A to A[j].
• If A + … + A[j] is exactly K, note this down and subtract A to get the sum from A.
• Otherwise, we continue to add A[j+1] etc until we reach a value where the sum crosses K and repeat the argument above.

Essentially we maintain a sliding window within which we maintain the sum. At each stage:

• if the sum of the window is less than K, expand the window to the right.
• if the sum of the window is greater to K, contract the window from the left.
• if the sum of the window is equal to K, note the left and right end points and contract the window from the left.

Example

```      K = 8

1    3    2    1    4    1    3    2    1    1    2
```

Expand window right till sum crosses K

```      1    3    2    1    4    1    3    2    1    1    2
|--->4--->6--->7-->11
```

Exceeds K, contract window from left

```      1    3    2    1    4    1    3    2    1    1    2
|------------>10
```

Exceeds K, contract window from left

```      1    3    2    1    4    1    3    2    1    1    2
|------->7
```

Less than K, expand window to right

```      1    3    2    1    4    1    3    2    1    1    2
|------------->8
```

Equals K, note left and right end points, contract from left

```      1    3    2    1    4    1    3    2    1    1    2
|-------->6
```

Less than K, expand window to right

```      1    3    2    1    4    1    3    2    1    1    2
|------------->9
```

Exceeds K, contract window from left

```      1    3    2    1    4    1    3    2    1    1    2
|-------->8
```

Equals K, note left and right end points, contract from left

```      1    3    2    1    4    1    3    2    1    1    2
|--->4
```

Less than K, expand window to right

```      1    3    2    1    4    1    3    2    1    1    2
|--->4--->6--->7--->8
```

Equals K, note left and right end points, contract from left

```      1    3    2    1    4    1    3    2    1    1    2
|------------->7
```

Less than K, expand window to right

```      1    3    2    1    4    1    3    2    1    1    2
|------------->7--->9
```

Exceeds K, contract window from left

```      1    3    2    1    4    1    3    2    1    1    2
|------------->7
```

Less than K, cannot expand window to right, stop