First negative integer in every window of size k
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]
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;}