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 = 3printFirstNegativeInteger(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