Deque Pattern — First Negative in Every Window

What does it solve?

For every window of size k, report the first negative number (0 if none). A rescan per window is O(N·k); a deque of candidate indices makes it O(N).

Key insight: a deque (add/remove at both ends) holds the indices of negatives currently in the window, oldest at the front. Push a new negative's index at the back; pop from the front when it slides out of the window. The front is always the earliest negative still in range, so it's the answer. This two-ended access is exactly what a plain queue or stack can't do alone → O(N).

The core idea

for i in 0..n-1:
  if dq.front <= i-k: dq.popFront() # expire
  if a[i] < 0: dq.pushBack(i) # candidate
  if i >= k-1:
    out = dq.empty ? 0 : a[dq.front]

Complexity

Time complexity

O(N)

Each index is pushed to the back once and popped from the front once, so total deque work is linear regardless of k.

Space complexity

O(k)

The deque holds at most the negatives inside one window, bounded by k.

Examples & edge cases

Live animation — deque of negative indices, front = answer

incoming a[i] in window pushed to back deque front = answer

nums · k = —

Deque of negative indices (front = oldest)

empty

First negative per window (0 = none)

none yet

Current step detail

i = — deque = — front = — answers = —

Step — of —

incoming i

—

nums[i]

deque size

—

candidates

front value

—

first negative

windows done

—

emitted

Select an example and press Play to start.

✓ Done

SpeedMedium

Step-by-step table

Step	i	nums[i]	pop front	push back	deque	emit

C++ implementation

first_negative_window.cpp

#include <bits/stdc++.h>
using namespace std;

// First negative in every window of size k (0 if none), using a deque
vector<int> firstNegative(vector<int>& a, int k) {
    deque<int> dq;              // indices of negatives, oldest at front
    vector<int> res;

    for (int i = 0; i < (int)a.size(); i++) {
        // expire indices that left the window from the front
        if (!dq.empty() && dq.front() <= i - k) dq.pop_front();

        if (a[i] < 0) dq.push_back(i);   // new candidate at the back

        if (i >= k - 1)                  // window complete
            res.push_back(dq.empty() ? 0 : a[dq.front()]);
    }
    return res;
}

int main() {
    vector<int> a = {12,-1,-7,8,-15,30,16,28};
    for (int x : firstNegative(a, 3)) cout << x << " "; // -1 -1 -7 -15 -15 0
    return 0;
}

My Notes

📝Notes✅

▼

●Start typing to save...0 chars

Practice this problem