Skip to content
Katabench
Try free

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

C#
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.

C# coding challenges →

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