Indian Computing Olympiad

Sliding Window Algorithms

Buying empty plots

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[1], A[2], … 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 N². Can we do better?

The prefix sums form a sequence of values in ascending value:
P[1] < P[2] < … < 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[1]. Add A[2], A[3], …

• 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[1].
• At this point, we subtract A[1] from the sum. We automatically have the sum starting from A[2] upto A[j].
• The sum from A[2] upto A[j-1] must be less than K (since the sum from A[1] to A[j-1] was less than K). If there is already a solution for A[2], it must be A[2] to A[j].
• If A[2] + … + A[j] is exactly K, note this down and subtract A[2] to get the sum from A[3].
• 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