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

/div>

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  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)