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[] firstNegativeInWindow(int[] arr, int k) {
int n = arr.length;
int[] result = new int[n - k + 1];
Deque<Integer> negativeIndices = new ArrayDeque<>(); // holds indices of negatives, in order, within the current window
for (int right = 0; right < n; right++) {
if (arr[right] < 0) negativeIndices.addLast(right);
if (right >= k - 1) {
// drop indices that have fallen out of the window's left edge
while (!negativeIndices.isEmpty() && negativeIndices.peekFirst() <= right - k) {
negativeIndices.pollFirst();
}
int windowStart = right - k + 1;
result[windowStart] = negativeIndices.isEmpty() ? 0 : arr[negativeIndices.peekFirst()];
}
}
return result;
}Time: O(n) · Space: O(k) worst case for the deque