Count of Range Sum - Practice Coding Problems

Count of Range Sum - Problem

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

Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive.

Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.

Input & Output

Example 1 — Basic Case

$ Input: nums = [-2,5,-1], lower = -2, upper = 2

› Output: 3

💡 Note: Three range sums in [-2,2]: subarray [-2] sum=-2, subarray [-1] sum=-1, subarray [5,-1] sum=4. Wait, 4 is not in [-2,2]. Let me recalculate: [-2] sum=-2 ✓, [5] sum=5 ✗, [-1] sum=-1 ✓, [-2,5] sum=3 ✗, [5,-1] sum=4 ✗, [-2,5,-1] sum=2 ✓. So we have 3 valid sums.

Example 2 — Single Element

$ Input: nums = [0], lower = 0, upper = 0

› Output: 1

💡 Note: Only one possible range sum: [0] which equals 0, and 0 is in range [0,0]

Example 3 — No Valid Ranges

$ Input: nums = [-3,-1], lower = 1, upper = 2

› Output: 0

💡 Note: All possible sums are negative: [-3]=-3, [-1]=-1, [-3,-1]=-4. None are in range [1,2]

Constraints

1 ≤ nums.length ≤ 10⁵
-2³¹ ≤ nums[i] ≤ 2³¹ - 1
-10⁵ ≤ lower ≤ upper ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums=[-2,5,-1], range=[-2,2]

Process

Find all subarrays with sum in [-2,2]

Output

Count = 3 valid range sums

Key Takeaway

🎯 Key Insight: Transform to prefix sum differences and use divide & conquer for optimal O(n log n) counting

Asked in

G Google 35 M Microsoft 28 a Amazon 22

The key insight is to convert the problem to counting prefix sum differences. The optimal approach uses merge sort with divide and conquer to efficiently count cross-boundary range sums. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	Calculate every possible subarray sum and count those in range
Prefix Sum with Two Pointers	O(n²)	O(n)	Use prefix sums to convert range sum problem to difference problem
Merge Sort with Counting	O(n log n)	O(n)	Use divide and conquer with merge sort to efficiently count range sums

Brute Force — Algorithm Steps

For each starting index i
For each ending index j >= i, calculate sum from i to j
Count sums that fall in [lower, upper] range

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All Subarrays

Use nested loops to create every possible subarray

Calculate Sum

For each subarray, compute the sum of elements

Count Valid Sums

Count sums that fall within [lower, upper] range

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int lower, int upper) {
    int count = 0;
    
    for (int i = 0; i < numsSize; i++) {
        long long currentSum = 0;
        for (int j = i; j < numsSize; j++) {
            currentSum += nums[j];
            if (currentSum >= lower && currentSum <= upper) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int numsSize = 0;
    char *token = strtok(line + 1, ",]"); // Skip opening bracket
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int lower, upper;
    scanf("%d", &lower);
    scanf("%d", &upper);
    
    int result = solution(nums, numsSize, lower, upper);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops: outer loop runs n times, inner loop runs up to n times

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables to track sum and count

✓ Linear Space

78.0K Views

Medium Frequency

~35 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler