## Problem statement

Given an array of integers `a`, and a positive integer `k`, find the first negative integer for each and every window (contiguous subarray) of size `k`. If a window does not contain a negative integer, then print 0 for that window.

Example 1

``````Input: a[] = {-5, 1, 2, -6, 9}, k = 2
Output : -5 0 -6 -6

Explanation: First negative integer in every window of size 2
{-5, 1} = -5
{1, 2} = 0 (does not contain a negative integer)
{2, -6} = -6
{-6, 9} = -6``````

Example 2

``````Input : a[] = {10, -1, -5, 7, -15, 20, 18, 24} , k = 3
Output : -1 -1 -5 -15 -15 0
Explanation: First negative integer in every window of size 3
{10, -1, -5} = -1
{-1, -5, 7} = -1
{-5, 7, -15} = -5
{7, -15, 20} = -15
{-15, 20, 18} = -15
{20, 18, 24} = 0 (does not contain a negative integer)``````

## Solution

### Brute force

The naive brute force approach is to run two for loops to find the first negative number in every subarray of size `k`.

The outer loop runs for every index `i` of the array and the inner loop explores the next `k` elements to find the first negative number in the subarray (`i` to `i+k`).

The time complexity for this algorithm is `O(n*k)`.

``````import java.util.Scanner;

class FirstNegativeNumber {
private static int[] findFirstNegativeNumberInSubarrayOfSizeK_BruteForce(int[] a, int k) {
int n = a.length;
int[] firstNegativeNumbers = new int[n - k + 1];
int idx = 0;

for(int i = 0; i <= n-k; i++) {
int firstNegativeNum = 0;
for(int j = i; j < i+k; j++) {
if(a[j] < 0) {
firstNegativeNum = a[j];
break;
}
}
firstNegativeNumbers[idx++] = firstNegativeNum;
}

return firstNegativeNumbers;
}

public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();

int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = keyboard.nextInt();
}

int k = keyboard.nextInt();

keyboard.close();

int[] firstNegativeNumbers = findFirstNegativeNumberInSubarrayOfSizeK_BruteForce(a, k);
for (int i = 0; i < firstNegativeNumbers.length; i++) {
System.out.print(firstNegativeNumbers[i] + " ");
}
System.out.println();
}
}``````

### Sliding Window

If you closely observe the way we calculate the first negative number in each subarray of size `k` in the brute force algorithm, you will realize that we are doing repetitive work. Let’s consider the first example:

``Input: a[] = {10, -1, -5, 7, -15, 20, 18, 24}, k = 3``

In the brute force approach, we first find the first negative number in the subarray `{10, -1, -5}`, then we move to the next subarray and find the first negative number in the subarray `{-1, -5, 7}`. Notice that there is an overlap between both the subarrays:

``````10 -1 -5
-1 -5 7``````

So, we’re exploring the overlapping part (`{-1, -5}`) twice. Can we explore the overlapping subarray only once and reduce the repetitive work? Yes, and this hints us towards using the Sliding window pattern.

Sliding window pattern

• Consider each subarray of size `k` as a sliding window.
• Initialize two variables `windowStart` and `windowEnd` pointing to the first element of the array. These variables define the bounds of our sliding window. The initial window size is `1`.
• Initialize a FIFO queue that stores the negative numbers in the current window in a First-in-First-Out order.
• Iterate over the array moving `windowEnd` forward by one element in each iteration.
• If the new element pointed by `windowEnd` is negative, then add it to the queue.
• If the window size hits to `k` (`windowEnd-windowStart+1 == k`), then
• Find the first negative number in the current window by getting the first element from the queue and store it in the result.
• If the queue is empty, that means the current window (current subarray) did not have any negative number, so store `0` in the result.
• Now we need to slide the window ahead. So we need to discard the element at `windowStart` out of the window. To do this -
• Check if the first element in the queue is equal to the element at `windowStart`, if yes then remove it from the queue since it is going out of the window.
• Increment `windowStart` to slide the window ahead.
``````import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class FirstNegativeNumber {
private static int[] findFirstNegativeNumberInSubarrayOfSizeK(int[] a, int k) {
int n = a.length;
int[] firstNegativeNumbers = new int[n - k + 1];
int idx = 0;

int windowStart = 0;
for (int windowEnd = 0; windowEnd < n; windowEnd++) {
if (a[windowEnd] < 0) {
}

if (windowEnd - windowStart + 1 == k) { // Calculate result and Slide the window
if (q.isEmpty()) {
firstNegativeNumbers[idx++] = 0;
} else {
int num = q.peek();
firstNegativeNumbers[idx++] = num;

// Remove a[windowStart] from the queue since we need to slide the window now.
// But only if it was added to the queue previously
if (num == a[windowStart]) {
q.remove();
}
}
windowStart++; // Slide the window ahead
}
}

return firstNegativeNumbers;
}

public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();

int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = keyboard.nextInt();
}

int k = keyboard.nextInt();

keyboard.close();

int[] firstNegativeNumbers = findFirstNegativeNumberInSubarrayOfSizeK(a, k);
for (int i = 0; i < firstNegativeNumbers.length; i++) {
System.out.print(firstNegativeNumbers[i] + " ");
}
System.out.println();
}
}``````