Stage 1 · Code
Stacks & Queues
Deque
Double-ended queue for sliding window max/min problems.
5 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Deque Concept
A deque (double-ended queue) allows O(1) insertion/removal at both front and rear. Go's container/list provides doubly-linked list which works as deque. Can also implement with circular array.
Godeque-with-container/list.go
20 linesLn 1, Col 1Go
`container/list` is a doubly-linked list. PushFront/PushBack/Remove all O(1). Front()/Back() access ends.
Monotonic Deque
A monotonic deque maintains elements in sorted order (increasing or decreasing). When adding new element, remove from back all elements that violate monotonicity. Front always holds min/max.
Gomonotonic-deque-for-sliding-window-max.go
27 linesLn 1, Col 1Go
Deque stores indices of potential maxes in decreasing order. Remove expired indices from front. Remove smaller values from back (they'll never be max). Front is always window max. O(n) total.
Sliding Window Maximum
Given array and window size k, find max in each window. Brute force O(nk). Monotonic deque achieves O(n). Each element pushed/popped at most once.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.