Window Sums Within a Band

Hard

You are given an integer array values and two integers low and high. For every contiguous non-empty window of the array, take the sum of its elements. Return the number of windows whose sum lies between low and high, inclusive. Windows with different boundaries count separately, even when their sums are equal. Checking every window takes O(n²); try to do better.

Example 1

values=[3, -4, 2], low=-1, high=1 → 2

The window sums are [3] = 3, [-4] = -4, [2] = 2, [3, -4] = -1, [-4, 2] = -2 and [3, -4, 2] = 1. Two of them, -1 and 1, fall between -1 and 1.

Example 2

values=[5, 5, 5], low=10, high=10 → 2

Two windows, each made of two neighbouring 5s, sum to 10.

Example 3

values=[0, 0], low=0, high=0 → 3

All three windows ([0], [0] and [0, 0]) sum to 0.

Constraints

1 ≤ len(values) ≤ 10⁵
-10¹⁰ ≤ values[i] ≤ 10¹⁰
-10¹⁰ ≤ low ≤ high ≤ 10¹⁰

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Binary Indexed Tree Segment Tree Array Binary Search Divide and Conquer Ordered Set Merge Sort

Similar problems

Smaller Values to the Right Hard Pairs With a Steep Drop Hard Cost of Filling a Sorted Shelf Hard Triples Both Rankings Agree On Hard Pairs Within a Shifted Gap Hard

Input

values=[3, -4, 2], low=-1, high=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 102 tests on the server, hidden ones included.