To solve the problem of finding the first negative number in every window of size k in an array, we can use a sliding window approach. I’ll explain the brute force, better, and optimal approaches in C++, providing code along with a dry run for each.

Problem Statement:

Given an array arr[] and an integer k, find the first negative number in every window of size k. If there is no negative number in the window, print 0.

---

1. Brute Force Approach

In the brute force approach, we will loop through each window of size k and find the first negative number. This approach has a time complexity of O(n * k) because for each window of size k, we are scanning through the elements.

Code:

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

void firstNegativeNumberBruteForce(vector<int>& arr, int k) {
    int n = arr.size();
    for (int i = 0; i <= n - k; i++) {
        bool found = false;
        for (int j = i; j < i + k; j++) {
            if (arr[j] < 0) {
                cout << arr[j] << " ";
                found = true;
                break; // exit as soon as we find the first negative number
            }
        }
        if (!found) {
            cout << "0 "; // No negative number in the window
        }
    }
    cout << endl;
}

int main() {
    vector<int> arr = {12, -1, -7, 8, -15, 30, 16, 28};
    int k = 3;
    firstNegativeNumberBruteForce(arr, k);
    return 0;
}

Explanation:

• We iterate through each window of size k.
• For each window, we look for the first negative number.
• If no negative number is found, we print 0.

Dry Run:

For arr = [12, -1, -7, 8, -15, 30, 16, 28] and k = 3:

1. Window 1: [12, -1, -7] → The first negative number is -1. Print -1.
2. Window 2: [-1, -7, 8] → The first negative number is -1. Print -1.
3. Window 3: [-7, 8, -15] → The first negative number is -7. Print -7.
4. Window 4: [8, -15, 30] → The first negative number is -15. Print -15.
5. Window 5: [-15, 30, 16] → The first negative number is -15. Print -15.
6. Window 6: [30, 16, 28] → No negative number, so print 0.

Output:

-1 -1 -7 -15 -15 0

Time Complexity:

• O(n * k) where n is the length of the array, and k is the window size.

2. Better Approach (Using a Queue)

In the better approach, we can optimize the brute force solution by using a queue to store the indices of negative numbers. This reduces the time complexity to O(n), as we are iterating through the array only once.

Explanation of Better Approach:

• We maintain a deque (dq) to store indices of negative numbers.
• For each new window, we:
  • Remove elements from the front of the deque that are out of the current window.
  • Add the current negative number to the deque.
  • Output the first negative number in the deque or 0 if there are no negative numbers.

class Solution {
  public:
    vector<int> FirstNegativeInteger(vector<int>& arr, int k) {
        // write code here
        deque<int>dq;
        vector<int>ans;
        int n = arr.size();
        
        // Process the first window
        for(int i = 0; i < k; i++) {
            if(arr[i] < 0) dq.push_back(i);
        }
        
        // Add the result for the first window
        if(!dq.empty()) ans.push_back(arr[dq.front()]);
        else ans.push_back(0);

        // Process the remaining windows
        for(int i = k; i < n; i++) {
            // Remove elements that are out of the current window
            while(!dq.empty() && dq.front() <= i - k) dq.pop_front();
            
            // Add the current element to the deque if it's negative
            if(arr[i] < 0) dq.push_back(i);
            
            // Add the result for the current window
            if(!dq.empty()) ans.push_back(arr[dq.front()]);
            else ans.push_back(0);
        }
        
        return ans;
    }
};

Dry Run Step-by-Step:

1. Initialize the deque to store indices of negative numbers in the window.
2. Process the first window (first k elements) separately:
   • The first window contains the elements [12, -1, -7] (i.e., indices 0 to 2).
   • We iterate through the window and find the negative numbers.
3. Start processing the rest of the array from index k to n-1.
   • For each new window, we:
     • Print the first negative number from the deque.
     • Remove indices that are out of the window.
     • Add the current negative number (if any) to the deque.

Dry Run for

arr = [12, -1, -7, 8, -15, 30, 16, 28] and k = 3:

1. First Window: Indices 0 to 2 ([12, -1, -7])
   • For indices 0 to 2, we check the negative numbers:
     • arr[0] = 12 → not negative.
     • arr[1] = -1 → negative, so add index 1 to the deque.
     • arr[2] = -7 → negative, so add index 2 to the deque.
   • Now, the deque contains indices [1, 2], pointing to -1 and -7.
   • First negative number: -1 (because index 1 is the first in the deque).
   • Output so far: -1
2. Window 2: Indices 1 to 3 ([-1, -7, 8])
   • Remove indices that are out of the window:
     • 1 is still in the window, so we don’t remove it.
     • 2 is still in the window, so we don’t remove it.
   • Add the new element arr[3] = 8, which is not negative.
   • The deque still contains indices [1, 2].
   • First negative number: -1 (because index 1 is still the first in the deque).
   • Output so far: -1 -1
3. Window 3: Indices 2 to 4 ([-7, 8, -15])
   • Remove indices that are out of the window:
     • Index 1 is out of the window, so we remove it.
   • The deque now contains [2] (pointing to -7).
   • Add the new element arr[4] = -15, which is negative, so we add index 4 to the deque.
   • The deque now contains [2, 4].
   • First negative number: -7 (because index 2 is still the first in the deque).
   • Output so far: -1 -1 -7
4. Window 4: Indices 3 to 5 ([8, -15, 30])
   • Remove indices that are out of the window:
     • Index 2 is out of the window, so we remove it.
   • The deque now contains [4] (pointing to -15).
   • Add the new element arr[5] = 30, which is not negative.
   • The deque still contains [4].
   • First negative number: -15 (because index 4 is still the first in the deque).
   • Output so far: -1 -1 -7 -15
5. Window 5: Indices 4 to 6 ([-15, 30, 16])
   • Remove indices that are out of the window:
     • Index 4 is still in the window.
   • The deque now contains [4] (pointing to -15).
   • Add the new element arr[6] = 16, which is not negative.
   • The deque still contains [4].
   • First negative number: -15 (because index 4 is still the first in the deque).
   • Output so far: -1 -1 -7 -15 -15
6. Window 6: Indices 5 to 7 ([30, 16, 28])
   • Remove indices that are out of the window:
     • Index 4 is out of the window, so we remove it.
   • The deque is now empty.
   • Add the new element arr[7] = 28, which is not negative.
   • The deque is empty, so no negative number is found.
   • First negative number: 0 (since the deque is empty).
   • Output so far: -1 -1 -7 -15 -15 0

Final Output:

-1 -1 -7 -15 -15 0

Time Complexity:

• O(n), where n is the length of the array.

Conclusion:

• Brute Force Approach: O(n * k) — Simply iterate over each window and find the first negative number.
• Better Approach: O(n) — Use a deque to keep track of negative numbers in the window, leading to a much faster solution.