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?