Frontend School

Count Range Sum

DSA
hard

Count Range Sum

Hard
Arrays
Divide and Conquer
Prefix Sum
Merge Sort

Overview

As a data analyst at a leading financial firm, you are tasked with identifying specific cumulative trends in stock market data. Your team is particularly interested in finding periods where the total profit or loss over a contiguous stretch of days falls within a predefined acceptable range. This analysis helps in understanding market volatility and identifying stable investment windows.

What you need to do / Task

Given an integer array nums representing daily changes in stock price (where nums[i] is the change on day i), and two integers lower and upper, your task is to implement a function that returns the number of contiguous subarrays whose sum lies within the inclusive range [lower, upper].

A contiguous subarray is defined by its start and end indices i and j (inclusive, i <= j). Its sum is nums[i] + nums[i+1] + ... + nums[j].

Input & output

function countRangeSum(nums: number[], lower: number, upper: number): number

  • nums: An array of integers representing daily changes in stock price.
  • lower: An integer, the lower bound of the target sum range (inclusive).
  • upper: An integer, the upper bound of the target sum range (inclusive).
  • Returns: An integer, the total count of valid range sums.

Clarifications

  • Empty nums: If nums is empty, there are no subarrays, so the count should be 0.
  • Negative numbers: nums can contain negative, zero, or positive integers.
  • lower > upper: If lower is strictly greater than upper, no sum can satisfy the range, so the count should be 0.
  • Large sums: The sums of subarrays can exceed standard 32-bit integer limits. Ensure your implementation uses a data type capable of holding 64-bit integer values (e.g., number in JavaScript/TypeScript, long in Java/C++) for prefix sums to prevent overflow.

Examples

1

Example 1

Input:

nums = [-2, 5, -1], lower = -2, upper = 2

Output:

3

Note:

The three subarrays whose sums fall in the range [-2, 2] are:

  1. [-2] with sum -2
  2. [-1] with sum -1
  3. [-2, 5, -1] with sum 2
2

Example 2

Input:

nums = [0], lower = 0, upper = 0

Output:

1

Note:

The subarray [0] has a sum of 0, which is within the range [0, 0].

3

Example 3

Input:

nums = [1, 1, 1], lower = 1, upper = 2

Output:

5

Note:

The five subarrays with sums in [1, 2] are:

  1. [1] (index 0) sum = 1
  2. [1] (index 1) sum = 1
  3. [1] (index 2) sum = 1
  4. [1, 1] (indices 0-1) sum = 2
  5. [1, 1] (indices 1-2) sum = 2

Constraints

Constraints & assumptions

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • -10^15 <= lower <= upper <= 10^15
  • The final answer is guaranteed to fit in a 32-bit integer.
  • The solution should aim for optimal time complexity, typically O(N log N).

Out of scope

  • Input validation (e.g., ensuring nums is an array of numbers, lower and upper are integers).
  • Optimizations for specific input patterns (e.g., all zeros, pre-sorted nums).
  • Parallelizing the computation.

What interviewers evaluate

  • Algorithmic Correctness: The solution must correctly identify all subarray sums within the specified range, handling edge cases and large number sums without overflow.
  • Time and Space Complexity: The candidate is expected to derive and implement an O(N log N) time complexity solution using Divide and Conquer (e.g., a modified merge sort), with O(N) auxiliary space.
  • Code Quality: The code should be well-structured, readable, and maintainable, demonstrating good programming practices.
  • Communication: The candidate should clearly articulate their thought process, explain the chosen algorithm, analyze its complexity, and justify design decisions.

Loading editor...