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.
leave a comment
0 Comments