First negative integer in every window of size k

Medium

Problem

For every contiguous window of size k, report its first negative number, or 0 if the window has none.

Example 1

Input:  arr = [-8, 2, 3, -6, 10], k = 2
Output: [-8, 0, -6, -6]

Also asked as: First negative integer in every window of size “k”

Test cases

Case 1

Input:    [-8,2,3,-6,10], 2
Expected: [-8,0,-6,-6]

Case 2

Input:    [12,-1,-7,8,-15,30,16,28], 3
Expected: [-1,-1,-7,-15,-15,0]

Case 3

Input:    [1,2,3], 1
Expected: [0,0,0]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Deque of indices of negatives

Time O(n)Space O(k)

Maintain a queue of indices of negative numbers in the current window; the front is the answer, and it is popped when it slides out.

function firstNegativeEachWindow(a, k) {
const dq = [], res = [];
for (let i = 0; i < a.length; i++) {
if (a[i] < 0) dq.push(i);
if (i >= k - 1) {
while (dq.length && dq[0] <= i - k) dq.shift();
res.push(dq.length ? a[dq[0]] : 0);
}
}
return res;
}