Count Bounded Range Sums
Hard About 40 min Free, no account needed
Count signed subarray totals inside an inclusive band without enumerating quadratic pairs.
The brief
Return the number of nonempty contiguous subarrays whose sum lies in the inclusive interval [lower, upper]. Values may be negative, and equal sums at different positions count separately.
Solve([-2, 5, -1], -2, 2) returns 3: [-2], [-1], and [-2, 5, -1].
There are at most 200,000 signed 32-bit values. Bounds satisfy -10^15 <= lower <= upper <= 10^15. Return a 64-bit count. Empty input returns 0; do not change the input. Negative values rule out a window that assumes sums only grow, and large cases rule out trying every start/end pair.
Starter code
using System;
public class Solution
{
public long Solve(int[] values, long lower, long upper)
{
// TODO: implement the contract without changing the input.
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Divide and conquer
- Split the input, solve the halves, and count or combine across the split, as merge sort does.
- Prefix sums
- Carry running totals or prefix state so any range question becomes a lookup.
Do these first
Related katas
- Longest Well-Performing Interval Hard Free Longest stretch of days with more tiring days than easy ones.
- Shortest Subarray With Sum at Least K Hard Free Find the shortest target-reaching interval when negative values break the usual window.
- Contiguous Array Medium Free Longest subarray holding as many zeros as ones.
- Product of Array Except Self Medium Free For each index, return the product of all other elements, without division.