Tutorialspoint.dev

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


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.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter