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

©IARCS 2012–2016

PÄ›stujeme web | visit: Skluzavky