Please read the new rule regarding the restriction on the use of AI tools. ×

[Tutorial] Minimum Deque

Revision en2, by k1r1t0, 2023-11-04 02:14:05

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English k1r1t0 2023-11-04 02:14:05 2 (published)
en1 English k1r1t0 2023-11-04 02:13:19 3176 Initial revision (saved to drafts)