Skip to content
RED SAGSkills
hard60 ptsprefix-sumsorting

Count Range-Bounded Sums

Return how many non-empty contiguous subarrays of nums have a sum s with lower <= s <= upper.

An O(n^2) scan is too slow for the largest inputs.

Example 1

Input: nums = [1, 2, 3], lower = 3, upper = 3
Output: 2
Explanation: [1, 2] and [3].

Example 2

Input: nums = [-2, 5, -1], lower = -2, upper = 2
Output: 3
Explanation: [-2], [-1] and [-2, 5, -1].

Constraints

  • 0 <= nums.length <= 3 * 10^4
  • -10^5 <= nums[i] <= 10^5
  • -10^9 <= lower <= upper <= 10^9
Hint 1

Subarray (i, j] has sum pre[j] - pre[i], so count pairs of prefix sums.

Hint 2

During a merge sort of the prefix sums, both halves are sorted; for each left value two moving pointers find the matching range in the right half.

Discussion 0

Join free to post in the discussion.

Good practice for: Data Scientist, Data Engineer, Machine Learning Engineer, AI Engineer (LLM & Generative AI), Backend Developer, Blockchain Developer

Run checks your code on 2 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.