# First negative integer in every window of size k

Given an array 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 interger, 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
```

Naive Approach: Run two loops. In the outer loop, take all subarrays(windows) of size k. In the inner loop, get the first negative integer of the current subarray(window).

## C++

 `// C++ implementation to find the first negative  ` `// integer in every window of size k ` `#include ` `using` `namespace` `std; ` `  `  `// function to find the first negative  ` `// integer in every window of size k ` `void` `printFirstNegativeInteger(``int` `arr[], ``int` `n, ``int` `k) ` `{ ` `    ``// flag to check whether window contains ` `    ``// a negative integer or not ` `    ``bool` `flag; ` `     `  `    ``// Loop for each subarray(window) of size k ` `    ``for` `(``int` `i = 0; i<(n-k+1); i++)            ` `    ``{ ` `        ``flag = ``false``; ` ` `  `        ``// traverse through the current window ` `        ``for` `(``int` `j = 0; j

## Java

 `// Java implementation to find the first negative  ` `// integer in every window of size k ` `import` `java.util.*; ` ` `  `class` `solution ` `{ ` ` `  `// function to find the first negative  ` `// integer in every window of size k ` `static` `void` `printFirstNegativeInteger(``int` `arr[], ``int` `n, ``int` `k) ` `{ ` `    ``// flag to check whether window contains ` `    ``// a negative integer or not ` `    ``boolean` `flag; ` `     `  `    ``// Loop for each subarray(window) of size k ` `    ``for` `(``int` `i = ``0``; i<(n-k+``1``); i++)          ` `    ``{ ` `        ``flag = ``false``; ` ` `  `        ``// traverse through the current window ` `        ``for` `(``int` `j = ``0``; j

## Python3

 `# Python3 implementation to find the first negative  ` `# integer in every window of size k ` ` `  `# Function to find the first negative  ` `# integer in every window of size k ` `def` `printFirstNegativeInteger(arr, n, k): ` `     `  `    ``# Loop for each subarray(window) of size k ` `    ``for` `i ``in` `range``(``0``, (n ``-` `k ``+` `1``)): ` `        ``flag ``=` `False` ` `  `        ``# Traverse through the current window ` `        ``for` `j ``in` `range``(``0``, k): ` `         `  `            ``# If a negative integer is found, then ` `            ``# it is the first negative integer for  ` `            ``# current window. Print it, set the flag ` `            ``# and break ` `            ``if` `(arr[i ``+` `j] < ``0``): ` `         `  `                ``print``(arr[i ``+` `j], end ``=` `" "``) ` `                ``flag ``=` `True` `                ``break` `         `  `        ``# If the current window does not ` `        ``# contain a negative integer ` `        ``if` `(``not``(flag)): ` `            ``print``(``"0"``, end ``=` `" "``) ` `     `  `# Driver Code ` `arr ``=` `[``12``, ``-``1``, ``-``7``, ``8``, ``-``15``, ``30``, ``16``, ``28``] ` `n ``=` `len``(arr) ` `k ``=` `3` `printFirstNegativeInteger(arr, n, k) ` ` `  `# This code is contributed by 'Smitha dinesh semwal' `

## C#

 `// C# implementation to find  ` `// the first negative integer ` `// in every window of size k  ` `using` `System; ` ` `  `class` `GFG ` `{  ` ` `  `// function to find the first negative  ` `// integer in every window of size k  ` `static` `void` `printFirstNegativeInteger(``int` `[]arr,  ` `                                    ``int` `n, ``int` `k)  ` `{  ` `    ``// flag to check whether window contains  ` `    ``// a negative integer or not  ` `    ``bool` `flag;  ` `     `  `    ``// Loop for each subarray(window) of size k  ` `    ``for` `(``int` `i = 0; i < (n - k + 1); i++)  ` `    ``{  ` `        ``flag = ``false``;  ` ` `  `        ``// traverse through the current window  ` `        ``for` `(``int` `j = 0; j < k; j++)  ` `        ``{  ` `            ``// if a negative integer is found, then  ` `            ``// it is the first negative integer for  ` `            ``// current window. Print it, set the flag  ` `            ``// and break  ` `            ``if` `(arr[i + j] < 0)  ` `            ``{  ` `                ``Console.Write((arr[i + j]) + ``" "``);  ` `                ``flag = ``true``;  ` `                ``break``;  ` `            ``}  ` `        ``}  ` `         `  `        ``// if the current window does not  ` `        ``// contain a negative integer  ` `        ``if` `(!flag)  ` `            ``Console.Write(``"0"` `+ ``" "``);  ` `    ``}  ` `}  ` ` `  `// Driver code ` `public` `static` `void` `Main(String []args)  ` `{  ` `    ``int` `[]arr = {12, -1, -7, 8, -15, 30, 16, 28};  ` `    ``int` `n = arr.Length;  ` `    ``int` `k = 3;  ` `    ``printFirstNegativeInteger(arr, n, k);  ` `}  ` `}  ` ` `  `// This code has been contributed ` `// by 29AjayKumar `

Output :

```-1 -1 -7 -15 -15 0
```

Time Complexity : The outer loop runs n-k+1 times and the inner loop runs k times for every iteration of outer loop. So time complexity is O((n-k+1)*k) which can also be written as O(nk) when k is comparitively much smaller than n, otherwise when k tends to reach n, complexity becomes O(k).

Efficient Approach: It is a variation of the problem of Sliding Window Maximum.
We create a Dequeue, Di of capacity k, that stores only useful elements of current window of k elements. An element is useful if it is in the current window and it is a negative integer. We process all array elements one by one and maintain Di to contain useful elements of current window and these useful elements are all negative integers. For a particular window, if Di is not empty then the element at front of the Di is the first negative integer for that window, else that window does not contain a negative integer.

 `// C++ implementation to find the first negative  ` `// integer in every window of size k ` `#include ` ` `  `using` `namespace` `std; ` `  `  `// function to find the first negative  ` `// integer in every window of size k ` `void` `printFirstNegativeInteger(``int` `arr[], ``int` `n, ``int` `k) ` `{ ` `    ``// A Double Ended Queue, Di that will store indexes of  ` `    ``// useful array elements for the current window of size k. ` `    ``// The useful elements are all negative integers. ` `    ``deque<``int``>  Di; ` `  `  `    ``/* Process first k (or first window) elements of array */` `    ``int` `i; ` `    ``for` `(i = 0; i < k; i++) ` `        ``// Add current element at the rear of Di ` `        ``// if it is a negative integer ` `        ``if` `(arr[i] < 0) ` `            ``Di.push_back(i); ` `     `  `    ``// Process rest of the elements, i.e., from arr[k] to arr[n-1] ` `    ``for` `( ; i < n; i++) ` `    ``{ ` `        ``// if Di is not empty then the element at the ` `        ``// front of the queue is the first negative integer ` `        ``// of the previous window ` `        ``if` `(!Di.empty()) ` `            ``cout << arr[Di.front()] << ``" "``; ` `         `  `        ``// else the window does not have a ` `        ``// negative integer ` `        ``else` `            ``cout << ``"0"` `<< ``" "``; ` `  `  `        ``// Remove the elements which are out of this window ` `        ``while` `( (!Di.empty()) && Di.front() < (i - k + 1)) ` `            ``Di.pop_front();  ``// Remove from front of queue ` `  `  `        ``// Add current element at the rear of Di ` `        ``// if it is a negative integer ` `        ``if` `(arr[i] < 0) ` `            ``Di.push_back(i); ` `    ``} ` `  `  `    ``// Print the first negative  ` `    ``// integer of last window ` `    ``if` `(!Di.empty()) ` `           ``cout << arr[Di.front()] << ``" "``; ` `    ``else` `        ``cout << ``"0"` `<< ``" "``;        ` `     `  `} ` `  `  `// Driver program to test above functions ` `int` `main() ` `{ ` `    ``int` `arr[] = {12, -1, -7, 8, -15, 30, 16, 28}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr); ` `    ``int` `k = 3; ` `    ``printFirstNegativeInteger(arr, n, k); ` `    ``return` `0; ` `} `

Output:

```-1 -1 -7 -15 -15 0
```

Time Complexity: O(n)
Auxiliary Space: O(k)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

code

load comments