Minimum in sliding window: two different but similar solutions

Revision en12, by oversolver, 2019-11-24 16:53:28

Problem

There is are famous problem for given array of numbers and number $$$K$$$ find minimums for all segments of length $$$K$$$.

More general variant: for given array of size $$$n$$$ and $$$q$$$ queries $$$[l_i,r_i]$$$ need to find minimums on segments at that $$$l_i \leq l_{i+1}$$$ and $$$r_i \leq r_{i+1}$$$. Solution must be $$$O(n+q)$$$.

To solve this problem we need sliding window method, where numbers from segments is window. Needed data structure should be able to push_back (add number to the end of window), pop_front (remove first element) and get_min — current minimum in window.

I was surprised to find that there are two types of such data structure. First is very popular and can be easily found in web. But type that I use whole life I can't find. I'll describe both of them.

Solution #1

The idea is to store sequence of increasing minimums. First minimum is minimum of whole window, second is minimum of elements after first minimum, and so on. For example, for window [2,3,1,5,4,8,7,6,9] sequence is [1,4,6,9].

When element is adding to the right of window (incR, push_back), the sequence changes as follows: all higher elements are gone from sequence, new element is goes to the end of sequence.

Couple of samples for [1,4,6,9]:

Adding 5: [1,4,6,9] -> [1,4] -> [1,4,5]

Adding 100: [1,4,6,9] -> [1,4,6,9,100]

Adding 0: [1,4,6,9] -> [] -> [0]

In removing left element from window (incL, pop_front) we need to know if first element of sequence is first element of window. Impossible to know this only by values, so we need to store sequence of pairs (value, index) except of only values. Previous example turns to [(1,2), (4,4), (6,7), (9,8)], where indices are numbered from zero. Bounds of window stored as pair of numbers $$$L$$$ and $$$R$$$. So, if first element of sequence is first element of window, that is its index equals to $$$L$$$, than only needed is to remove this first element from sequence.

Realization requires data structure that can efficiently perform operations of removing elements from left and right and adding new element to the right. Here we can use deque (std::deque in c++).

solution #1

Solution #2

Represent window as two stacks: prefix of window stored in left stack $$$L$$$ so that first element of window in top of $$$L$$$, and suffix of window is stored in right stack $$$R$$$ so that last element of window in top of $$$R$$$.

[2,3,1,5,4,8,7,6,9]
<-------|--------->

L = [5,1,3,2]
R = [4,8,7,6,9]

When element is adding to the right of window (incR, push_back), it just goes to the top of $$$R$$$.

In removing left element from window (incL, pop_front), its pops from $$$L$$$, except of case when $$$L$$$ is empty. In this case we need to move right stack to left: while $$$R$$$ is not empty top of $$$R$$$ goes to the top of $$$L$$$. Example:

[4,3,1,2]
|------->

L = []
R = [4,3,1,2]

L = [2]
R = [4,3,1]

L = [2,1]
R = [4,3]

L = [2,1,3]
R = [4]

L = [2,1,3,4]
R = []

[4,3,2,1]
<-------|

Now, after moving, we can pop top from $$$L$$$.

To get current minimum of window we need to know minimums of both stacks. Minimum of $$$R$$$ stored in $$$Rmin$$$ can be easily updated when elements are added to $$$R$$$.

In $$$L$$$ except of value need to store minimum of elements from this value to the bottom of stack. For example for stack [5,7,3,4,2,1,8,6] it is stack [5,5,3,3,2,1,1,1].

Thus, minimum in window is $$$Rmin$$$ or top of $$$L$$$.

solution #2

Notes

Personally, I think second solution is simpler for understanding, but first more easy to code.

Both solutions can be upgraded to operation push_front, but seems like its useless.

Tags sliding window, rmq, two pointers

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en15 English oversolver 2019-11-24 18:36:17 4 Tiny change: '\n\n`[4,3,2,1]` \n`<--' -> '\n\n`[4,3,1,2]` \n`<--'
ru44 Russian oversolver 2019-11-24 18:35:53 4 Мелкая правка: '\n\n`[4,3,2,1]` \n`<--' -> '\n\n`[4,3,1,2]` \n`<--'
ru43 Russian oversolver 2019-11-24 17:25:33 0 (опубликовано)
en14 English oversolver 2019-11-24 17:25:24 0 (published)
en13 English oversolver 2019-11-24 17:23:14 0 (saved to drafts)
ru42 Russian oversolver 2019-11-24 17:22:58 0 (сохранено в черновиках)
ru41 Russian oversolver 2019-11-24 16:54:03 0 (опубликовано)
en12 English oversolver 2019-11-24 16:53:28 0 (published)
ru40 Russian oversolver 2019-11-24 16:52:35 25
en11 English oversolver 2019-11-24 16:51:14 29
en10 English oversolver 2019-11-24 16:45:56 941
en9 English oversolver 2019-11-24 16:01:26 466
en8 English oversolver 2019-11-24 15:49:46 671
en7 English oversolver 2019-11-24 15:43:22 342
en6 English oversolver 2019-11-24 15:38:43 868
en5 English oversolver 2019-11-24 15:31:33 762
en4 English oversolver 2019-11-24 15:25:13 24
en3 English oversolver 2019-11-24 15:23:39 5343
ru39 Russian oversolver 2019-11-24 15:05:07 14 Мелкая правка: 'евый стек.\n\n \n`[4,3,1,' -> 'евый стек. Например,\n\n`[4,3,1,'
ru38 Russian oversolver 2019-11-24 15:03:45 39 Мелкая правка: ' `get_min`~--- текущи' -> ' `get_min`--- текущи'
ru37 Russian oversolver 2019-11-24 15:01:33 419
ru36 Russian oversolver 2019-11-24 14:56:46 36
ru35 Russian oversolver 2019-11-24 14:56:03 386
ru34 Russian oversolver 2019-11-24 14:46:41 4 Мелкая правка: 'зков длины.\n\nБолее' -> 'зков длины $K$.\n\nБолее'
ru33 Russian oversolver 2019-11-24 14:46:07 376
ru32 Russian oversolver 2019-11-24 11:22:46 60
ru31 Russian oversolver 2019-11-24 11:21:05 165
ru30 Russian oversolver 2019-11-24 11:12:19 311
ru29 Russian oversolver 2019-11-24 11:10:10 314
ru28 Russian oversolver 2019-11-24 11:04:23 20 Мелкая правка: '### Решени' -> '### Задача\n\n\n\n\n### Решени'
ru27 Russian oversolver 2019-11-24 11:02:40 148
ru26 Russian oversolver 2019-11-24 11:02:31 378
ru25 Russian oversolver 2019-11-24 10:53:43 712 Мелкая правка: ',7,6,9]` `<------' -> ',7,6,9]` `<------'
ru24 Russian oversolver 2019-11-24 10:47:16 4 Мелкая правка: ',8,7,6,9]`\n`<-------|' -> ',8,7,6,9]` `<-------|'
ru23 Russian oversolver 2019-11-24 10:47:03 128
ru22 Russian oversolver 2019-11-24 10:44:01 11 Возвращено к ru20
ru21 Russian oversolver 2019-11-24 10:43:27 11
ru20 Russian oversolver 2019-11-24 10:40:25 25 Мелкая правка: 'имер, для последовательности `[2,3,1,5' -> 'имер, для значений в окне `[2,3,1,5'
ru19 Russian oversolver 2019-11-24 10:39:48 12
ru18 Russian oversolver 2019-11-24 10:39:12 24
ru17 Russian oversolver 2019-11-24 10:38:12 20
ru16 Russian oversolver 2019-11-24 10:32:22 6
ru15 Russian oversolver 2019-11-24 10:31:56 2 Мелкая правка: 'еров, для [1,4,6,9]:\n\nДобав' -> 'еров, для `[1,4,6,9]`:\n\nДобав'
ru14 Russian oversolver 2019-11-24 07:56:10 18
ru13 Russian oversolver 2019-11-24 07:55:41 15 Мелкая правка: 'Решение #1\n---------\n\nИдея в' -> '### Решение #1\n\nИдея в'
ru12 Russian oversolver 2019-11-24 07:43:27 23
ru11 Russian oversolver 2019-11-24 07:42:18 23
ru10 Russian oversolver 2019-11-24 07:40:50 26 Мелкая правка: 'фывфыв\n\nИдея в' -> 'Решение 1\n---------\n\nИдея в'
ru9 Russian oversolver 2019-11-24 07:39:24 180
ru8 Russian oversolver 2019-11-24 07:36:11 875
ru7 Russian oversolver 2019-11-24 07:23:13 418
ru6 Russian oversolver 2019-11-24 06:45:55 3 Мелкая правка: 'mmary="2">~~~~~\nint' -> 'mmary="2">\n~~~~~\nint'
ru5 Russian oversolver 2019-11-24 06:41:58 9
ru4 Russian oversolver 2019-11-23 21:08:41 1 Мелкая правка: '\n\n<spoiler' -> '\n<spoiler'
en2 English oversolver 2019-11-23 21:08:19 5
ru3 Russian oversolver 2019-11-23 20:58:45 560
ru2 Russian oversolver 2019-11-23 20:49:46 676
ru1 Russian oversolver 2019-11-23 20:43:06 64 Первая редакция перевода на Русский (сохранено в черновиках)
en1 English oversolver 2019-11-23 20:42:15 69 Initial revision (saved to drafts)