Problem Statement:

Given an array of integers, we need to find the first negative number in every window of size k as the window slides from the start to the end of the array. If there is no negative number in a particular window, we should return 0 for that window.

Understanding the Sliding Window Concept:

The sliding window is a technique where we maintain a window of size k and slide it across the array to perform a specific task for every subset of size k.

Here In This Problem Statement ! , the task is to identify the first negative number in each window.

Approach to Solve this Problem:

1. Use a Deque to Track Negative Numbers:

   • A deque (double-ended queue) is used to store the indices of negative numbers in the current window. This data structure allows efficient insertion and deletion from both ends, which is crucial for managing the sliding window.

     Is Using a Deque Necessary?

     Yes, a deque is ideal for this problem because:

     1. It provides O(1) time complexity for adding and removing elements from both ends.
     2. It allows us to efficiently track the indices of negative numbers within the current window.

2. Sliding the Window:

   • Start by processing the first k elements and identify any negative numbers, storing their indices in the deque.
   • Then slide the window one element at a time. For each new element that enters the window:
     • Print the first negative number from the deque (if the deque is empty, print 0).
     • Remove any elements from the deque that are no longer in the window.
     • Add the index of the new element to the deque if it is negative.

3. Handling Edge Cases:

   • If the deque is empty at any point, meaning there are no negative numbers in the current window, we return 0 for that window.

Step-by-Step Dry Run with a Diagram:

Let's dry run the code on the array [1, 3, 7, 2, -3, -2, 12, 8, 6, 9] with a window size k = 3.

Initial Setup:

• Array: [1, 3, 7, 2, -3, -2, 12, 8, 6, 9]
• Window Size (k): 3
• Deque (dq): Empty initially.

Processing the First Window (First k elements):

1. Element 1 (Index 0):

   • 1 is not negative, so the deque remains empty.

2. Element 3 (Index 1):

   • 3 is not negative, so the deque remains empty.

3. Element 7 (Index 2):

   • 7 is not negative, so the deque remains empty.

Output for the First Window:

• The deque is empty, so output 0.

COOL ! UNDERSTOOD FIRST STEP ! :)

Next ! Sliding the Window:

4. Slide to Window [3, 7, 2]:

   • Element 2 (Index 3):
     • 2 is not negative, so the deque remains empty.
   • Output for this window: 0.

5. Slide to Window [7, 2, -3]:

   • Element -3 (Index 4):
     • -3 is negative, so we add its index (4) to the deque.
   • Output for this window: The first negative number is -3.

6. Slide to Window [2, -3, -2]:

   • Element -2 (Index 5):
     • -2 is negative, so we add its index (5) to the deque.
   • Output for this window: The first negative number is still -3 (from the deque).

7. Slide to Window [-3, -2, 12]:

   • Element 12 (Index 6):
     • 12 is not negative, so no changes to the deque.
   • Output for this window: The first negative number is -3 (from the deque).

8. Slide to Window [-2, 12, 8]:

   • Element 8 (Index 7):
     • 8 is not negative, so no changes to the deque.
   • The index of -3 is out of the current window, so we remove it from the deque.
   • Output for this window: The first negative number is -2.

9. Slide to Window [12, 8, 6]:

   • Element 6 (Index 8):
     • 6 is not negative, so no changes to the deque.
   • The index of -2 is out of the current window, so we remove it from the deque.
   • Output for this window: The deque is empty, so output 0.

10. Slide to Window [8, 6, 9]:

    • Element 9 (Index 9):
      • 9 is not negative, so no changes to the deque.
    • Output for this window: The deque is empty, so output 0.

Final Output:

0 0 -3 -3 -3 -2 0 0

Visual Diagram:

Table Explanation:

• Window: The current sliding window.
• Indices: The start and end indices of the current window in the array.
• Elements: The elements in the current window.
• Deque (dq) State: The indices of negative numbers currently in the deque. This deque stores the indices of negative numbers in the window, allowing us to access the first negative number efficiently.
• Output: The first negative number in the window, or 0 if there are no negatives.

😎 COOL 

LETS UNDERSTAND THE CODE 

#include <deque>    // Needed for deque
#include <vector>   // Needed for vector
#include <iostream> // Needed for standard I/O
using namespace std;

// Function to find the first negative number in every sliding window of size k
void slidingWindow(vector<int> v, int k) {
    deque<int> dq;  // Deque to store the indices of negative numbers
    int size = v.size();

    // Step 1: Process the first window of size k
    for (int i = 0; i < k; i++) {
        if (v[i] < 0) {
            dq.push_back(i); // Store the index of negative number
        }
    }

    // Step 2: Process the rest of the array
    for (int i = k; i < size; i++) {
        // Output the first negative number of the current window
        if (dq.empty()) {
            cout << 0 << " ";
        } else {
            cout << v[dq.front()] << " ";
        }

        // Remove elements that are out of this window
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // Add the current element if it's negative
        if (v[i] < 0) {
            dq.push_back(i);
        }
    }

    // Output the first negative number of the last window
    if (dq.empty()) {
        cout << 0 << " ";
    } else {
        cout << v[dq.front()] << " ";
    }

    cout << endl; // Move to the next line after output
}

int main() {
    vector<int> v = {1, 3, 7, 2, -3, -2, 12, 8, 6, 9}; // Example array
    int k = 3; // Window size

    slidingWindow(v, k); // Call the function

    return 0;
}

Whats Happening in the Code !  :

• Step 1: Processing the first window: We push the indices of negative numbers within the first k elements into the deque.
• Step 2: Processing the remaining elements: For each new element, we:
  1. Print the first negative number in the current window.
  2. Remove indices that are no longer within the window range.
  3. Add the index of the current element if it's negative.
• Step 3: Final Output: After exiting the loop, we need to ensure that the last window is also considered.

Key Points to Remember:

• Sliding Window Technique: Focus on maintaining the state of the window as it slides across the array.
• Deque Efficiency: Deque allows for efficient management of the window’s elements, especially when you need to handle specific conditions like finding the first negative.
• Edge Cases: Consider cases where there are no negatives in a window and ensure the deque is correctly updated when elements go out of the window.

Complexity Analysis:

• Time Complexity: O(n) - We process each element once, and each element is added and removed from the deque at most once.
• Space Complexity: O(k) - The deque holds at most k elements (indices of the negative numbers within the window).

This approach effectively handles the sliding window problem while ensuring clarity and ease of understanding, especially for those new to data structures and algorithms.

GREAT !