Given an array arr of integers and a positive integer k, find the first negative integer in every contiguous window of size k. If a window contains no negative integer, output 0 for that window.
Example 1
Input: arr = [12,-1,-7,8,-15,30,16,28], k = 3
Output: [-1,-1,-7,-15,-15,0,0]
Explanation: Each window of size 3 slides by one; its first negative number (or 0 if none) is reported.
Example 2
Input: arr = [-8,2,3,-6,10], k = 2
Output: [-8,0,-6,-6]
Explanation: Window [-8,2] -> -8; [2,3] -> 0 (no negative); [3,-6] -> -6; [-6,10] -> -6.
1 <= k <= arr.length <= 10^5-10^5 <= arr[i] <= 10^5Recomputing 'find the first negative' by scanning each window from scratch is O(n*k) — what state can you carry between windows instead?
A deque holding only the indices of negative numbers currently in the window, in order, tells you the answer for the current window in O(1): the front, if any.
When the window slides, an index might fall out the left side — how do you know when the deque's front is no longer in the window?
public int[] firstNegativeInWindowBruteForce(int[] arr, int k) {
int n = arr.length;
int[] result = new int[n - k + 1];
for (int i = 0; i + k <= n; i++) {
int firstNeg = 0;
for (int j = i; j < i + k; j++) {
if (arr[j] < 0) { firstNeg = arr[j]; break; }
}
result[i] = firstNeg;
}
return result;
}Time: O(n*k) · Space: O(1) extra beyond the output