Count Window Sums Within Bounds
A meter records signed changes nums. A window is any contiguous block nums[i..j] with i <= j. Count the windows whose sum S satisfies lower <= S <= upper.
Checking every window is O(n²) and too slow for the large tests. Work with prefix sums and count valid pairs while merge-sorting them.
Example 1
Input: nums = [-2,5,-1], lower = -2, upper = 2 Output: 3 Explanation: The windows [-2], [-1] and [-2,5,-1] qualify.
Example 2
Input: nums = [1,-1,2,-2,3], lower = 0, upper = 1 Output: 6
Constraints
- 0 <= nums.length <= 2 * 10^4
- -10^4 <= nums[i] <= 10^4
- -10^8 <= lower <= upper <= 10^8
Hint 1
A window sum is pre[j + 1] - pre[i], so count pairs of prefix sums whose difference lies in the bounds.
Hint 2
During merge sort, for each left-half prefix, two moving pointers over the sorted right half find how many right-half prefixes fit.
Discussion 0
Join free to post in the discussion.
Good practice for: Data Engineer, Data Scientist, Backend Developer, Site Reliability Engineer, Machine Learning Engineer
Run checks your code on 3 sample tests. Submit runs all 9 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.