Given an array and a positive integer k, find the first negative integer for each window(contiguous subarray) of size k. If a window does not contain a negative integer, then print 0 for that window.
Examples:
Input : arr[] = {-8, 2, 3, -6, 10}, k = 2
Output : -8 0 -6 -6
First negative integer for each window of size k
{-8, 2} = -8
{2, 3} = 0 (does not contain a negative integer)
{3, -6} = -6
{-6, 10} = -6
Input : arr[] = {12, -1, -7, 8, -15, 30, 16, 28} , k = 3
Output : -1 -1 -7 -15 -15 0
public class Solution {
public int[] solve(int[] A, int B) {
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < B; i++) {
if (A[i] < 0)
q.add(i);
}
int[] ans = new int[A.length - B + 1];
ans[0] = q.size() > 0 ? A[q.peek()] : 0;
for (int i = B; i < A.length; i++) {
if (A[i] < 0)
q.add(i);
if (q.size() > 0 && q.peek() <= i - B)
q.poll();
ans[i - B + 1] = q.size() > 0 ? A[q.peek()] : 0;
}
return ans;
}
}