First Negative Integer in Every Window of Size K

You are given an array of n integers and an integer k. For every contiguous window of size k, as it slides from left to right across the array, report the first negative number that appears in that window. If a window contains no negative number, report 0 for that window.

Input: The first line contains two space-separated integers n and k. The second line contains n space-separated integers representing the array. Output: Print n - k + 1 space-separated integers on a single line: the first negative number of each window in order, or 0 if a window has none.

1 <= k <= n <= 10^5 -10^5 <= arr[i] <= 10^5

This is a lighter-weight cousin of 'Sliding Window Maximum' - instead of maintaining a full monotonic deque of ALL values, you only need to track the (typically much smaller) subset of negative values, since only THOSE are ever relevant to the answer.

For every fixed-size window sliding across an array, report the first negative number found within it, or 0 if there is none. Brute force: For every window, scan all k elements directly looking for the first negative one - this costs O(n*k), unnecessary when a queue of negative indices can track this incrementally. Optimised: Maintaining a queue of ONLY the negative numbers' indices (in order) and lazily dropping ones that fall out of range means each negative index is added and removed from the queue AT MOST ONCE across the whole algorithm - giving true O(n) total work despite processing n windows.

1. Keep a QUEUE (or deque) of INDICES of negative numbers seen so far, in increasing order. 2. Before reading the answer for a window, drop indices from the FRONT of the queue that have fallen outside the current window's left boundary. 3. The FRONT of the queue, if any remains, is the first negative number in the current window; otherwise, the answer is 0.

Time: O(n) - each negative index enters and leaves the queue at most once. Space: O(k) in the worst case, for the queue of negative indices within the current window.

Handle k = 1 (each window is a single element, so the answer for that window is the element itself if negative, otherwise 0) and k = n (a single window covering the whole array). Windows with no negative numbers at all must print 0.

Be ready to explain why only tracking NEGATIVE indices (not all indices) keeps the queue small and the lookups fast - there's no need to track positive numbers at all, since they never matter for this specific question.