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