Negative Window

The Problem

Given an integer array arr and an integer k, return a list where each element represents the count of negative numbers in the corresponding window of size k as it slides from left to right. The result has n − k + 1 elements — one per window position.

arr = [-1, 2, -3, 4, -5],  k = 3  →  [2, 1, 2]
arr = [1, 2, 3, 4],         k = 2  →  [0, 0, 0]
arr = [-1, -2, -3],         k = 2  →  [2, 2]
arr = [-5, 1, -1, 2, -3],  k = 3  →  [2, 1, 2]

Examples

Example 1

Input:  arr = [-1, 2, -3, 4, -5],  k = 3
Output: [2, 1, 2]
Explanation:
  Window 1: [-1, 2, -3] → 2 negatives
  Window 2: [2, -3, 4]  → 1 negative
  Window 3: [-3, 4, -5] → 2 negatives

Example 2

Input:  arr = [1, 2, 3, 4],  k = 2
Output: [0, 0, 0]
Explanation: No negatives in any window.

Example 3

Input:  arr = [-1, -2, -3],  k = 2
Output: [2, 2]
Explanation: Every window of size 2 contains 2 negatives.

Intuition

The aggregate here is the count of negative numbers in the current window. When the window slides one step:

• If the element entering from the right is negative → neg_count += 1
• If the element leaving from the left is negative → neg_count -= 1
• Non-negative elements entering or leaving don’t affect the count

Unlike Maximum Ones (which tracked the best count) or Subarray Size Equals K (which tracked a match count), this problem records the count for every window position. The result is an array, not a single number.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  subgraph W1["Window [-1, 2, -3]: neg_count=2"]
    direction LR
    A["-1"] --- B["2"] --- C["-3"] --- D["4"] --- E["-5"]
    PS1(["start=0"]) --> A
    PE1(["end=2"]) --> C
  end
  subgraph W2["Window [2, -3, 4]: neg_count=1"]
    direction LR
    A2["-1✗"] --- B2["2"] --- C2["-3"] --- D2["4"] --- E2["-5"]
    PS2(["start=1"]) --> B2
    PE2(["end=3"]) --> D2
  end
  subgraph W3["Window [-3, 4, -5]: neg_count=2"]
    direction LR
    A3["-1✗"] --- B3["2✗"] --- C3["-3"] --- D3["4"] --- E3["-5"]
    PS3(["start=2"]) --> C3
    PE3(["end=4"]) --> E3
  end
  W1 -->|"remove -1 (-1), add 4 (+0) → neg=1"| W2
  W2 -->|"remove 2 (+0), add -5 (+1) → neg=2"| W3

Each slide removes the outgoing element's contribution and adds the incoming one. The count updates in O(1) — one conditional check per side per step.

Solution

from typing import List

class Solution:
    def count_negatives_per_window(self, arr: List[int], k: int) -> List[int]:
        # Initialize the window boundaries
        start     = 0
        end       = 0
        # Running count of negative numbers in the current window
        neg_count = 0
        result    = []

        while end < len(arr):
            # ① Expand: if the incoming element is negative, increment the count
            if arr[end] < 0:
                neg_count += 1

            # ② Contract: if window grew past k, evict the outgoing element
            if end - start + 1 > k:
                # Remove the outgoing element's contribution to the negative count
                if arr[start] < 0:
                    neg_count -= 1
                start += 1

            # ③ Process: when window is exactly k, record the count for this window
            if end - start + 1 == k:
                result.append(neg_count)

            end += 1

        return result


sol = Solution()
print(sol.count_negatives_per_window([-1, 2, -3, 4, -5], 3))   # [2, 1, 2]
print(sol.count_negatives_per_window([1, 2, 3, 4], 2))          # [0, 0, 0]
print(sol.count_negatives_per_window([-1, -2, -3], 2))          # [2, 2]
print(sol.count_negatives_per_window([-5, 1, -1, 2, -3], 3))   # [2, 1, 2]
print(sol.count_negatives_per_window([-3], 1))                  # [1]

Dry Run — Example 1

arr = [-1, 2, -3, 4, -5], k = 3

start=0, end=0, neg_count=0, result=[]

end=0: ① arr[0]=-1 < 0 → neg=1. size=1, not k.
end=1: ① arr[1]=2 ≥ 0  → neg=1. size=2, not k.
end=2: ① arr[2]=-3 < 0 → neg=2. ③ size=3==k → result=[2].
end=3: ① arr[3]=4 ≥ 0  → neg=2. ② size=4>k → arr[0]=-1 < 0 → neg=1, start=1.
       ③ size=3==k → result=[2, 1].
end=4: ① arr[4]=-5 < 0 → neg=2. ② size=4>k → arr[1]=2 ≥ 0 → neg=2, start=2.
       ③ size=3==k → result=[2, 1, 2].
end=5: end >= n=5 → loop exits.

Return: [2, 1, 2] ✓

Window [-1,2,-3] → 2 negatives: -1 and -3
Window [2,-3,4]  → 1 negative:  -3
Window [-3,4,-5] → 2 negatives: -3 and -5

Result Size

The result always has exactly n − k + 1 elements — one per valid window. For n=5, k=3: 5 − 3 + 1 = 3 windows, 3 results. This is consistent with all fixed sliding window “report per window” problems.

Complexity Analysis

Edge Cases

Key Takeaway

Negative Window demonstrates recording per-window results rather than a single aggregate maximum or count. The aggregate (count of negatives) still updates in O(1) per slide via a conditional increment/decrement. The result array grows by one entry each time the window reaches full size — this is the ③ process step of the template, here recording instead of comparing.