Code Logo

Count Windows With Negative Sum

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given an integer array and window size k, count how many contiguous subarrays of length k have a sum less than 0 using the sliding window technique.

This is the complement of the positive-sum problem. Maintain the running window sum. After each slide, check if the sum is negative and increment the counter. The sliding window update subtracts the leaving element and adds the entering element in O(1) time per slide.

The time complexity is O(n) with a single pass through the array. The space complexity is O(1) using only integer variables for the running sum and the count.

Edge cases include empty arrays (return 0), k larger than array length (return 0), and arrays where all window sums are non-negative (return 0).

This is the complement of the positive-sum problem and follows the same sliding window pattern. The condition check is simply inverted from > 0 to< 0.

The window-sum-negative problem is the direct complement of window-sum-positive. Together, these two problems show how the same sliding window pattern can be adapted to different threshold conditions. The running sum update is identical — only the comparison operator changes from > 0 to < 0. This demonstrates the versatility of the sliding window approach across different problem requirements.

Example Input & Output

Example 1
Input
[-5],1
Output
1
Example 2
Input
[0,-1,-2],2
Output
2
Explanation

[0,-1]=-1, [-1,-2]=-3

Example 3
Input
[-5,4,3],2
Output
1
Explanation

Only [-5,4]=-1 is negative

Example 4
Input
[-1,-2,5,6],2
Output
1
Explanation

Only [-1,-2]=-3 is negative

Example 5
Input
[],2
Output
0

Algorithm Flow

Recommendation Algorithm Flow for Count Windows With Negative Sum

Solution Approach

Given an array of integers and a window size k, count how many subarrays of length k have a negative sum. Use a sliding window to maintain the running sum incrementally. For each window, check if the sum is less than 0. Count the number of windows with negative sums.

function countNegativeSumWindows(arr, k) {
  if (k > arr.length) return 0;
  var sum = 0, count = 0;
  for (var i = 0; i < k; i++) sum += arr[i];
  if (sum < 0) count++;
  for (var i = k; i < arr.length; i++) {
    sum = sum - arr[i - k] + arr[i];
    if (sum < 0) count++;
  }
  return count;
}

The sliding window updates in O(1) per position instead of O(k) for a naive recalculation. Negative numbers contribute to making the sum negative; positive numbers can offset them.

Time complexity is O(n), space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(int[] nums, int k) {
        if (nums.length<k) return 0;
        int s=0;for(int i=0;i<k;i++)s+=nums[i];
        int r=s<0?1:0;
        for(int i=k;i<nums.length;i++){s+=nums[i]-nums[i-k];if(s<0)r++;}
        return r;
    }
}