Rs
Data Structures for Interviews
Module 4Stack, Queue & DequeLesson 17 of 2324 min

Deque: Both Ends & Sliding Window

push/pop front and back; monotonic deque for sliding window max.

Full deque ops

rust
q.push_front(x);
q.push_back(x);
q.pop_front();
q.pop_back();
q.front(); q.back();

Sliding window maximum

Maintain deque of indices with decreasing values:

  1. Pop back while nums[back] <= nums[i]
  1. Push i
  1. Pop front if out of window
  1. Front is max for window ending at i

Time O(n). Classic hard interview favorite.

Challenge

Sliding window minimum by flipping the comparison.

Tips
  • Store indices not values
  • Monotonic deque
  • Amortized O(n)

Try it live

Deque: Both Ends & Sliding WindowRust 2021
Loading editor…
Output
Press Run to compile and execute.