2)First negative integer in every window of size k - (sliding window)

Given an array A[] of size N and a positive integer K, find the first negative integer for each and every window(contiguous subarray) of size K.


Example 1:

Input : 
N = 5
A[] = {-8, 2, 3, -6, 10}
K = 2
Output : 
-8 0 -6 -6
Explanation :
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
 
Example 2:

Input : 
N = 8
A[] = {12, -1, -7, 8, -15, 30, 16, 28}
K = 3
Output :
-1 -1 -7 -15 -15 0 




c++  implementation:

vector<long long> printfunc(long long a[],long long n, long long k) 
{
        int i=0; int j=0;
        vector<long long>v;
        queue<long long>q;
        while(j<n)
        {
            if(a[j]<0)
            q.push(a[j]);
    
            if(j-i+1>=k)
            {
                if(j-i+1>k)
                {
                    if(a[i]==q.front())
                    {
                        q.pop();
                    }
                    i++;
                }
                if(q.empty())
                v.push_back(0);
                else
                v.push_back(q.front());
            }
            
            j++;
        }                                           
        return v;                                       
                                                 
}
time complexity: O(n)
space complexity: O(1)











darkmode