Indian Computing Olympiad

Training Material

Sliding Window Algorithms→Min Segments

You are given a sequence of N integers x1, x2, …, xN, where N can be as large as 106. You are also given an interval length M, where M can be as large as 105. The goal is to report the minimum of every segment of M numbers in the list.

In other words, the output should be

  • min (x1,x2,...,xM)
  • min (x2,...,xM,xM+1)
  • min (x3,...,xM+1,xM+2)
  • …
  • min (x(N-M+1),...,xN-1,xN)

If we compute the minimum explicitly for each M segment of the input, we end up doing about O(NM) work, which is too much given the limits for each N and M.

Can we do better?

Solution

Break up the sequence into segments of length M.

For each segment y1 y2 … yi &hellip: yM, compute and store for each yi the two quantities min(y1,y2,…,yi) and min(yi,yi+1,…,yM). This can be done in two linear scans of y1,y2,hellip;,yM, one from left to right and one from right to left.

Now, if we ask for the minimum of some arbitrary interval of length M, it will in general span across two of the fixed intervals for which we have precomputed the values above. 

      y1 y2 ... yi-1 yi ... yM  z1 z2 ... zi-1 zi ... zM
                     |                      |
                     <---------------------->

We can compute min(yi,...,yM,z1,...,zi-1) from the precomputed values for these two intervals as min(min(yi...,yM), min(z1,...,zi-1)).

Thus, in one scan, we can use the precomputed values to compute the minimum for all values.

How much time does the precomputation take? We have to precompute values for N/M intervals. Each interval requires O(M) work, so overall we take about O(N) time for precomputation.

The final solution then takes another O(N) scan of the sequence with the precomputed values.

Notice that this technique can be applied to any function that is associative&emdash;e.g., max, gcd, …

It can also be applied in two dimensions. Suppose we have a large N×N array and we are looking for the maximum value in every M×M subarray of the large array.

We tile the N×N array into M×M arrays and for each (i,j) we compute the maximum with respect to the four small rectangles that it forms inside its M×M block. 

       -----------------------------------------
      |             |             |             |
      |             |             |             |
      |             |             |             |
      |             |             |             |
       -----------------------------------------
      |             |      |      |             |
      |             |      |      |             |
      |             |----(i,j)--- |------       |
      |             |      |      |      |      |
       --------------------+-------------+------
      |             |      |      |      |      |
      |             |      |      |      |      |
      |             |       ------+------       |
      |             |             |             |
       -----------------------------------------

Now, for an arbitrary M×M block that spans four of the original tiles, we combine the precomputed values for the four smaller rectangles that make up this M×M block.


Problems related to