### -kirito-'s blog

By -kirito-, history, 5 weeks ago,

Here I will describe a way to maintain deque that will allow us to find the smallest element in deque at any time. Maybe this technique is well-known, but I couldn’t find any info about it, so decided to post it there.

### Minimum Stack and Minimum Queue

First, we want to maintain stack with the ability to find its smallest element whenever we want. Let's store minimums on the corresponding prefix of stack along with elements. This way we can easily push/pop elements and find minimum in $O(1)$.

Minimum Queue can be maintained using two Minimum Stacks: one stack will store some elements from beginning, and the other from the end. We will push elements to the second stack and pop them from the first. If the first stack becomes empty, then we move all elements from the second stack into the first. It will work in $O(N)$ amortized.

### Minimum Deque

Actually, we can maintain Minimum Deque the same way we maintain Minimum Queue, but it will be too slow. The problem is the number of moved elements: in the worst case we will move all elements every operation by removing first and last element alternately. So instead of moving all elements let's move only a half of them at a time. Turns out it works in $O(N)$!

But how to prove it? Let $k_i$ be the number of elements deque contained right before $i_{th}$ operation, the algorithm above obviously works in $O(N + \sum k_i)$. Also $k_i = \frac{k_{i-1}}{2} + q_i$, where $q_i$ is the number of elements added between operations $i-1$ and $i$. We can see that $q_i$ contributes $q_i$ to $k_i$, $\frac{q_i}{2}$ to $k_{i+1}$, $\frac{q_i}{4}$ to $k_{i+2}$ and so on. It follows that $q_i$ contributes $O(q_i)$ to $O(\sum k_i)$. $\sum q_i$ is obviously $\leq N$, so $O(\sum k_i) = O(N)$. That's why the algorithm above is $O(N)$ amortized.

Implementation
• +210

 » 5 weeks ago, # |   -38 iirc this is well known in Japan and it is called SWAG (Sliding Window AGgregation). it's a pretty cool name I think
 » 5 weeks ago, # |   0 Aha, it can solve problems with the two pointers trick. Because the two pointers trick needs to remove $value(left)$, and so it can help to remove while maintaining $\min{value}$. I once saw it in a contest's tutorial (not on CodeForces), but I didn't think about it carefully, though.
 » 5 weeks ago, # |   0 Is it different from priority_queue ?
•  » » 5 weeks ago, # ^ |   +8 Did you read article?
•  » » 5 weeks ago, # ^ |   +8 Yes, but unlike the priority queue, when you delete an element in a minimum deque, you can delete the first element or the last one, when in the priority queue you can only delete the smallest one, in the priority queue you lose that order of the elements.
 » 5 weeks ago, # |   +62 this is well known in Croatia and it is called Monotnic Deque
•  » » 5 weeks ago, # ^ |   -10 I think monotonic queue is a different thing? Doesn't monotonic queue throw out unnecessary elements? I think it does if I am not mistaken
•  » » » 5 weeks ago, # ^ |   +17 And where did I mention monotonic queue :P
•  » » » » 5 weeks ago, # ^ |   +4 Oh yes I guess I am mistaken :facepalm: I think I was just thinking about another technique with a similar nameAnyways, it should be well known in various countries with various names.
 » 5 weeks ago, # |   +9 This is well known in Romania. I don't think it has a specific name.
•  » » 5 weeks ago, # ^ |   +3 i didn't know it ☹️
 » 5 weeks ago, # | ← Rev. 2 →   +27 A seemingly easier argument: Consider $\operatorname{abs}((\mathrm{the\ size\ of\ the\ first\ queue}) - (\mathrm{the\ size\ of\ second\ queue}))$ as the potential function. push/pop front/back increases the potential by at most 1, and the rebalance zeroes the potential function.
•  » » 5 weeks ago, # ^ |   +8 Also, as a historical note, this structure appeared first in Hoogerwoord's A symmetric set of efficient list operations in 1992. I learned this fact in Exercise 5.1 of Okasaki's Purely Functional Data Structure.
•  » » 5 weeks ago, # ^ |   +16 doesn't rebalance make it zero?
•  » » » 5 weeks ago, # ^ |   +3 oh yeah, you are right
 » 5 weeks ago, # |   -19
 » 5 weeks ago, # |   +30 One problem that require this ds RMI 2020 — Peru. The naive $O(nlogn)$ TLEs (time limit is $200ms$).
 » 5 weeks ago, # |   +8 I think the best name I have heard for this technique came from rainboy who called it "stabbing points."