Skip to content

Minimum Window

Specify a window length \(W\) and as you push new elements, it will tell you the smallest within \(W\) of the last element.

Code

Minimum Window
// Minimum Window {{{
// Be careful with case W = 0
struct MinWindow {
  int W;
  deque<pair<int, int>> Q;

public:
  explicit MinWindow(int W) : W(W) {}

  void push(int idx, int x) {
    while (!Q.empty() && Q.front().ff < idx-W+1) Q.pop_front();
    while (!Q.empty() && Q.back().ss >= x) Q.pop_back();
    Q.pb({idx, x});
  }

  int get() const { return Q.front().ss; }
};
//}}}

Problems

A couple problems where this is useful: