### k1r1t0's blog

By k1r1t0, history, 10 months 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

 » 10 months 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
 » 10 months 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.
 » 10 months ago, # |   0 Is it different from priority_queue ?
•  » » 10 months ago, # ^ |   +8 Did you read article?
•  » » 10 months 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.
 » 10 months ago, # |   +62 this is well known in Croatia and it is called Monotnic Deque
•  » » 10 months 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
•  » » » 10 months ago, # ^ |   +17 And where did I mention monotonic queue :P
•  » » » » 10 months 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.
 » 10 months ago, # |   +9 This is well known in Romania. I don't think it has a specific name.
•  » » 10 months ago, # ^ |   +3 i didn't know it ☹️
 » 10 months 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.
•  » » 10 months 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.
•  » » 10 months ago, # ^ |   +16 doesn't rebalance make it zero?
•  » » » 10 months ago, # ^ |   +3 oh yeah, you are right
 » 10 months ago, # |   -19
 » 10 months ago, # |   +30 One problem that require this ds RMI 2020 — Peru. The naive $O(nlogn)$ TLEs (time limit is $200ms$).
 » 10 months ago, # |   +8 I think the best name I have heard for this technique came from rainboy who called it "stabbing points."