# 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[0]
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[0].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[0]
# reset maxium for new values to 0
nw = 0
else
# shift supporting queue and
q.shift
qm = q[0]
# 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.)

Cheers]

shitpoet@gmail.com