GFG : First negative integer in every window of size k

Problem

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 
 

Your Task:  
You don't need to read input or print anything. Your task is to complete the function printFirstNegativeInteger() which takes the array A[], its size N and an integer K as inputs and returns the first negative number in every window of size K starting from the first till the end. If a window does not contain a negative integer , then return 0 for that window.


Expected Time Complexity: O(N)
Expected Auxiliary Space: O(K)

Solution-1

vector<long long> printFirstNegativeInteger(long long int A[],
                                             long long int N, long long int K) {
    vector<long long> ans;
    deque<int> dq;
    for(long long int i=0; i< N; i++) {
        while(!dq.empty() && dq.front() <= i-K) {
            //cout << "i1 : " << i << endl;
            //cout << "i2 : " << dq.front() << endl;
            dq.pop_front();
        }
        
        if(A[i] < 0) {
            dq.push_back(i);
        }
        //cout << "i : "<< i << ", A[i] : " << A[i] << ", dq front : " << dq.front() << endl;
        if(i>=K-1) {
            if(!dq.empty()) {
                //cout << "if i : " << i << "A[dq.front()] : " << A[dq.front()] << endl;
                ans.push_back(A[dq.front()]);
            }
            else {
                //cout << "else i : " << i << "0" << endl;
                ans.push_back(0);
            }
        }
        
    }
    return ans;
 }

Solution-2

vector<long long> printFirstNegativeInteger(long long int A[],
                                             long long int N, long long int k) {
    vector<long long> ans;
    
    queue<long long > negativeNo;
    long long int j = 0;

    for(j=0; j<k; j++) {
        if(A[j] < 0)
            negativeNo.push(A[j]);
    }
    
    if(!negativeNo.empty())
        ans.push_back(negativeNo.front());
    else
        ans.push_back(0);
    
    for(j=k; j<N; j++) {
        if(A[j-k] < 0) {
            negativeNo.pop();
        }
        
        if(A[j] < 0)
            negativeNo.push(A[j]);
        
        if(!negativeNo.empty())
            ans.push_back(negativeNo.front());
        else
            ans.push_back(0);
    }
    
    return ans;
 }