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 <bits/stdc++.h> 
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<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) 
            { 
                cout << arr[i+j] << " "; 
                flag = true; 
                break; 
            } 
        } 
          
        // if the current window does not 
        // contain a negative integer 
        if (!flag) 
            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[0]); 
    int k = 3; 
    printFirstNegativeInteger(arr, n, k); 
    return 0; 
} 

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<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) 
            { 
                System.out.print((arr[i+j])+" "); 
                flag = true; 
                break; 
            } 
        } 
          
        // if the current window does not 
        // contain a negative integer 
        if (!flag) 
            System.out.print("0"+" "); 
    }  
} 
  
// Driver program to test above functions 
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 is contributed by 
// Shashank_Sharma 

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 <bits/stdc++.h> 
  
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[0]); 
    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.

First negative integer in every window of size k

C++

Java

Python3

C#

tags:

You Might Also Like

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books