# Sliding window maximum in linear time

Given some array

``````a 5 3 6 7 4 6 1 2 9
``````

find maximum in each subarray of size `k`, in other words, in each sliding window of size `k`.

For example, for `k = 3`:

``````   a 5 3 6 7 4 6 1 2 9
win 5 3 6
. 3 6 7
. . 6 7 4
. . . 7 4 6
. . . . 4 6 1
. . . . . 6 1 2
. . . . . . 1 2 9
max 6 6 7 7 7 6 6 6 9
``````

For first glace you may have impression that this is easy. And you're right. But not as easy as linear search though. Supporting optimum in sliding window with `O(n)` complexity requires additional data structure, not just one variable.

But let's move from simple cases.

## Case of k = 1

In the case of window size equal to one element we just print the array.

``````for i in 0..m do
puts a[i].to_s
end
``````

And this is of course `O(n)`.

## Case of k = n

In the case of window size equal to array length, we search for one global maximum in the array.

``````max = a
for i in 1..m do
if a[i] > max
max = a[i]
end
end
puts max.to_s
``````

This is again `O(n)`.

## Solution for general case in polynomial time

This solution combines the two above.

``````for i in 0..n-k do
max = a[i]
for j in i+1..i+k-1 do
if a[i] > max
max = a[i]
end
end
puts max.to_s
end
``````

There're two loops, one over `n` and one over `k`, so the complexity is `O(n*k)`.

## Solution in linear time

What about `O(n)`?

To achieve `O(n)` we need to change previous solution a bit.

First, let's add an supporting queue, containing maximums of current window, for shifts `0..k-1`. This can be done in `O(k)` time:

``````def calc_q(a, i, k)
q = (i..(i+k-1)).to_a
max = 0
for j in 0..(k-1) do
jj = (k-1)-j
max = [max, a[i+jj]].max
q[jj] = max
end
q
end
``````

For `a = 5 3 6 7 4 6 1 2 9` and `k = 3` first window will be `5 3 6` and queue will be `6 6 6`, because `6` is the maximum value for all three subwindows: `5 3 6`, `3 6` and `6`:

``````win       5 3 6
subwin 0  5 3 6
subwin 1  . 3 6
subwin 2  . . 6
max       6 6 6 - this is the content of supporting queue for this window
``````

The trick to achieve `O(n)` time is to do building of this queue once per `k` elements, doing something like global maximum search for new values that aren't in the queue now at the same time.

``````q = calc_q(a, 0, k)
puts q.to_s
nw = 0
for i in 1..(n-k) do
if i % k == 0
# do rebuilding of supporting
# queue # once per k iterations
q = calc_q(a, i, k)
qm = q
# reset maxium for new values to 0
nw = 0
else
# shift supporting queue and
q.shift
qm = q
# and calc new max for new vals
# that arent in the queue for now
ai = a[i+k-1]
nw = [nw,ai].max
end
# calc maximum for the iteration
# as maxium of queue max and
# new values max values
m = [qm,nw].max
puts m.to_s
end
``````

This solution needs `O(k)` time each `k` iterations, so `O(n)` in total to support queue and `O(n)` time to do partial global maxium search. `O(n) + O(n) = O(n)`, so this is linear time.

Output:

``````[5, 3, 6, 7, 4, 6, 1, 2, 9]
q: 6 6 6
M: 6
[3, 6, 7]
q: 6 6
qm: 6
a[i+k-1]: 7
nw: 7
M: 7
[6, 7, 4]
q: 6
qm: 6
a[i+k-1]: 4
nw: 7
M: 7
[7, 4, 6]
q*: 7 6 6
M: 7
[4, 6, 1]
q: 6 6
qm: 6
a[i+k-1]: 1
nw: 1
M: 6
[6, 1, 2]
q: 6
qm: 6
a[i+k-1]: 2
nw: 2
M: 6
[1, 2, 9]
q*: 9 9 9
M: 9
``````

May be here can be better solutions. (But of course they can't be better asymptotically.)

Source code on gist.

Cheers]

shitpoet@gmail.com 