Indian Computing Olympiad

Sliding Window Algorithms→Min Segments

You are given a sequence of N integers x1, x2, …, xN, where N can be as large as 10⁶. You are also given an interval length M, where M can be as large as 10⁵. 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

---