Counting Negative Numbers in Every Window of Size k

Counting Negatives in Each Sliding Window

Imagine you have a list of numbers, and you want to look at them through a small "window" that shows only k numbers at a time. You start at the left, count how many of those k numbers are negative, then slide the window one step to the right and count again. You keep doing this until the window reaches the end of the list.

A subarray is just a small continuous chunk of the array. A subarray "of size k" means a chunk that holds exactly k numbers sitting next to each other.

The problem

You are given:

• an integer array arr
• a positive whole number k

Your job is to return a list. Each value in that list is the count of negative numbers inside one window of size k, going from left to right.

Walking through Example 1

arr = [4, -4, 5, -1, 4] and k = 3.

We slide a window of 3 numbers across the array:

1. First window: [4, -4, 5] → only -4 is negative → count is 1
2. Second window: [-4, 5, -1] → -4 and -1 are negative → count is 2
3. Third window: [5, -1, 4] → only -1 is negative → count is 1

So the answer is [1, 2, 1].

Notice the array has 5 numbers, and with a window of size 3 we get exactly 3 windows. The pattern is simple: number of windows = (length of array) − k + 1. Here that is 5 − 3 + 1 = 3.

Walking through Example 2

arr = [1, -2, 3, -5] and k = 1.

When k = 1, each window is just a single number. So for every number we simply ask: "Is this negative?" If yes, the count is 1; if no, the count is 0.

1. [1] → not negative → 0
2. [-2] → negative → 1
3. [3] → not negative → 0
4. [-5] → negative → 1

So the answer is [0, 1, 0, 1].

How to think about solving it

The simplest idea: for each starting position, look at the next k numbers and count the negatives. This works, but it re-checks the same numbers again and again.

A smarter idea is the sliding window trick. Instead of recounting from scratch each time, you keep a running count. When the window slides one step:

• the number leaving on the left — if it was negative, subtract 1 from your count
• the number entering on the right — if it is negative, add 1 to your count

This way you only do a tiny bit of work per slide, which is much faster for long arrays.

The function you need to write returns a vector<int> (a list of integers), where each integer is the negative-count for one window:

class Solution {
public:
    vector<int> negativeWindow(vector<int> &a
};