285. First Negative Integer in Every Window of Size K

Given an array of n integers and a window size k, for every contiguous window of size k (sliding from left to right across the array) print the first negative integer in that window, or 0 if the window has none. Print the results space-separated, in order.

Input: The first line contains an integer n. The second line contains n space-separated integers (which may be negative), the array. The third line contains k, the window size. Output: Print n-k+1 space-separated integers, one per window - the first negative number in that window, or 0 if it has none.

1 <= k <= n <= 10^5

This is very closely related to the 'sliding window maximum' family of problems (also solved with a deque of indices) - recognizing the shared underlying pattern (maintain a queue of 'still relevant' candidates, trimmed from the front as the window moves) transfers directly between them.

Slide a fixed-size window across an array, and for each position of the window, report the FIRST negative number inside it (or 0 if there are none). Brute force: For every window position, scan through all k elements in that window directly looking for the first negative one - this costs O(n*k) overall, which is slow when both n and k are large. Optimised: Maintaining a queue of just the negative indices still 'in play' means each index is added to the queue once and removed once across the ENTIRE scan (not once per window) - so instead of re-scanning the whole window every time, you only ever do a small amount of work as the window slides, giving a total cost proportional to n, not n times k.

Make one right-to-left pass over the array building a nextNeg array where nextNeg[i] is the index of the nearest negative number at or after position i (nextNeg[i] = i if arr[i] is negative, else nextNeg[i+1]). Then for each window starting at i, the answer is arr[nextNeg[i]] if nextNeg[i] <= i+k-1 (i.e., that negative actually falls inside the window), otherwise 0. This answers every window in O(1) after one linear precomputation pass, trading an O(n) auxiliary array for avoiding any per-window scanning. Time: O(n) Space: O(n)

Maintain a deque holding the indices of negative numbers currently inside the window, in left-to-right order. As the window slides one step at a time, pop the front index if it has fallen outside the window, and push the new incoming index onto the back if its value is negative; the answer for the current window is simply the value at the front of the deque, or 0 if the deque is empty. This achieves the same O(n) time as the precomputed-pointer approach but only ever stores indices that could plausibly still be inside some window, so its extra space is bounded by the window size k rather than the whole array. Time: O(n) Space: O(k)

For each of the n-k+1 windows, scan through all k elements of that window from left to right and stop at the first negative number found, printing 0 if none exists. This directly implements the definition of the problem but re-scans overlapping elements from window to window, doing up to k comparisons per window. Time: O(n*k) Space: O(1)

1. Keep a queue of INDICES (not values) of negative numbers that are still within the current window. 2. As the window slides right by one position, first remove any index from the FRONT of this queue that has fallen out of the window's left edge. 3. Then add the new incoming element's index to the BACK of the queue, but only if it's actually negative. 4. The front of this queue (if it's non-empty) is always the first negative number in the current window; if it's empty, the answer for this window is 0.

Time: O(n) overall - each array index enters and leaves the tracking queue at most once across the whole sliding process, regardless of the window size k. Space: O(k) in the worst case, for the queue of negative indices currently within the window.

k = n (a single window over the whole array); a window that contains no negative numbers at all (print 0); k = 1 (each window is one element).

This is a classic 'sliding window + monotonic-style queue' pattern - be ready to explain why tracking INDICES (not values) in the queue is essential, since you need to know when an index has aged out of the window, which a plain value wouldn't tell you.