Range Sum Query - Immutable - Practice Coding Problems

Range Sum Query - Immutable - Problem

Given an integer array nums, handle multiple queries of the following type:

Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

NumArray(int[] nums) Initializes the object with the integer array nums.
int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive.

Input & Output

Example 1 — Basic Range Queries

$ Input: nums = [-2,0,3,-5,2,-1], operations = [["sumRange",0,2],["sumRange",2,5],["sumRange",0,5]]

› Output: [1,-1,-3]

💡 Note: sumRange(0,2) = (-2) + 0 + 3 = 1, sumRange(2,5) = 3 + (-5) + 2 + (-1) = -1, sumRange(0,5) = (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

Example 2 — Single Element Range

$ Input: nums = [1,3,5], operations = [["sumRange",1,1],["sumRange",0,2]]

› Output: [3,9]

💡 Note: sumRange(1,1) = nums[1] = 3, sumRange(0,2) = 1 + 3 + 5 = 9

Example 3 — Full Array Range

$ Input: nums = [5,-3,5], operations = [["sumRange",0,0],["sumRange",1,2],["sumRange",0,2]]

› Output: [5,2,7]

💡 Note: sumRange(0,0) = 5, sumRange(1,2) = -3 + 5 = 2, sumRange(0,2) = 5 + (-3) + 5 = 7

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁵ ≤ nums[i] ≤ 10⁵
0 ≤ left ≤ right < nums.length
At most 10⁴ calls to sumRange

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums and multiple sumRange queries

Process

Build prefix sum array once, then use formula for each query

Output

Array of sum results for each query

Key Takeaway

🎯 Key Insight: Precompute prefix sums once to answer any range query in constant time

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to precompute prefix sums during initialization to enable O(1) range queries. Best approach is Prefix Sum with O(n) preprocessing and O(1) per query. Time: O(1) per query, Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum - Precompute Cumulative Sums	O(1)	O(n)	Build prefix sum array once, then answer queries in O(1)
Brute Force - Calculate Sum Each Time	O(n)	O(1)	For each query, iterate through the range and sum elements

Prefix Sum - Precompute Cumulative Sums — Algorithm Steps

Build prefix sum array where prefixSum[i] = sum of nums[0] to nums[i-1]
For sumRange(left, right), return prefixSum[right+1] - prefixSum[left]
This works because prefixSum[right+1] contains sum[0..right] and we subtract sum[0..left-1]

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Prefix Sum

prefixSum[i] = sum of nums[0] to nums[i-1]

Query Formula

sumRange(left, right) = prefixSum[right+1] - prefixSum[left]

Instant Result

O(1) calculation using subtraction

Code -

solution.c — C

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

typedef struct {
    int* prefixSum;
    int size;
} NumArray;

NumArray* createNumArray(int* nums, int numsSize) {
    NumArray* obj = malloc(sizeof(NumArray));
    obj->prefixSum = malloc((numsSize + 1) * sizeof(int));
    obj->size = numsSize + 1;
    obj->prefixSum[0] = 0;
    
    for (int i = 0; i < numsSize; i++) {
        obj->prefixSum[i + 1] = obj->prefixSum[i] + nums[i];
    }
    
    return obj;
}

int sumRange(NumArray* obj, int left, int right) {
    return obj->prefixSum[right + 1] - obj->prefixSum[left];
}

int* solution(int* nums, int numsSize, int** operations, int operationsSize, int* returnSize) {
    NumArray* numArray = createNumArray(nums, numsSize);
    int* results = malloc(operationsSize * sizeof(int));
    int resultCount = 0;
    
    for (int i = 0; i < operationsSize; i++) {
        int left = operations[i][0];
        int right = operations[i][1];
        results[resultCount++] = sumRange(numArray, left, right);
    }
    
    *returnSize = resultCount;
    free(numArray->prefixSum);
    free(numArray);
    return results;
}

int main() {
    int nums[] = {-2, 0, 3, -5, 2, -1};
    int numsSize = 6;
    
    int* ops[3];
    int op1[] = {0, 2}; ops[0] = op1;
    int op2[] = {2, 5}; ops[1] = op2;
    int op3[] = {0, 5}; ops[2] = op3;
    
    int returnSize;
    int* result = solution(nums, numsSize, ops, 3, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Each sumRange query is just one subtraction operation

✓ Linear Growth

Space Complexity

O(n)

Prefix sum array stores n+1 cumulative sum values

⚡ Linearithmic Space

285.0K Views

Medium Frequency

~15 min Avg. Time

3.2K 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

Prefix Sum - Precompute Cumulative Sums — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler