What is the time complexity of deque?

Worst case O(1) at both ends. Space complexity is O(n).

Deque

medium

O(1) push and pop at the front and the back. That combination is what makes the sliding-window maximum trick possible - every element enters and leaves exactly once.

Worst O(1) at both endsSpace O(n)

Loading the deque engine…

Where to go next

Queue

easy

First in, first out - and why list.pop(0) is a bug.

Monotonic stack

hard

Next greater element in one linear pass.

Variable sliding window

medium

Grow right, shrink left, never move backwards.