Queue • Sliding Window

First Negative Integer in Window

Given an array and an integer K, find the first negative integer for each and every window (contiguous subarray) of size K.

Try Interactive Simulator

The Queue (Deque)

We use a double-ended queue (or standard queue) to store the indices of negative numbers currently in our sliding window.

Expiring Old Data

As the window slides right, the index at the front of the queue might fall out of the window. We must `shift()` it out if `deque[0] <= i - K`.

Recording Answers

Once we've processed at least K elements, the front of the queue is guaranteed to be the FIRST negative number in our current window. If the queue is empty, there are no negatives.

12

[0]

-1

[1]

-7

[2]

8

[3]

-15

[4]

30

[5]

Deque (Indices)

Result Array

Code Tracker

:::

1let deque = []; let result = [];

2for (let i = 0; i < n; i++) {

3 if (deque.length > 0 && deque[0] <= i - k) {

4 deque.shift();

5 }

6 if (arr[i] < 0) {

7 deque.push(i);

8 }

9 if (i >= k - 1) {

10 if (deque.length > 0) result.push(arr[deque[0]]);

11 else result.push(0);

12 }

13}

14return result;

First Negative Window

First Negative Window

First Negative Integer in Window

The Queue (Deque)

Expiring Old Data

Recording Answers

First Negative Integer in Window

The Queue (Deque)

Expiring Old Data

Recording Answers