Log inSign up
easyLeetCodeNot Started

Range Sum Query - Immutable

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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

1. 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 (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Example 1 · Standard NumArray Queries:

Input: ["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output: [null, 1, -1, -3]
Explanation: NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]); - numArray.sumRange(0, 2) -> (-2) + 0 + 3 = 1 - numArray.sumRange(2, 5) -> 3 + (-5) + 2 + (-1) = -1 - numArray.sumRange(0, 5) -> (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

Example 2 · Single Element Query:

Input: ["NumArray", "sumRange"] [[[5]], [0, 0]]
Output: [null, 5]
Explanation: sumRange(0, 0) returns 5.

Constraints:

  • 1 <= nums.length <= 104
  • -105 <= nums[i] <= 105
  • 0 <= left <= right < nums.length
  • At most 104 calls will be made to sumRange.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Prefix sum definition and properties
  • Object-Oriented class design (Constructor vs Method)
  • Time complexity of repeated range queries

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Design and implement the canonical 1D Prefix Sum pattern.
  • Understand the 1-based indexing convenience for prefix arrays (prefix[0] = 0).
  • Analyze trade-offs between linear scan per query vs precomputed O(1) range queries.
  • Write clean Object-Oriented class definitions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • The underlying array is static / immutable (no updates).
  • There are a large number of contiguous range sum queries (e.g. up to 10,000 calls).
  • Need instantaneous O(1) response time per query.

Algorithmic Decision Tree:

  • Whenever multiple range sum queries are asked on an immutable array: Build a 1D Prefix Sum array of size N + 1 in the constructor.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Brute Force — Linear Iteration per Query

Intuition

Store the array as is. For each sumRange(left, right) call, loop from left to right and compute the sum on demand.

Algorithm

  1. Constructor: store reference to nums.
  2. sumRange(left, right):
  3. sum = 0.
  4. Loop i from left to right:
  5. sum += nums[i].
  6. Return sum.

Per-Query Linear Iteration (O(N) per Query)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Read first element in range
Visual state
Values and pointers at this exact step
pointers
S
-2
0
3
-5
2
-1
0
↑ i=0
1
2
3
4
5
Variables at this step
i
0
val
-2
sum
-2
Check / comparison
Query range [0..2]. Start at index 0: add nums[0] = -2
Decision / next transition
sum = -2.
Why this step matters

Read first element in range.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Brute Force: O(N) per query
6class NumArray {
7 vector<int> nums;
8public:
9 NumArray(vector<int>& nums) : nums(nums) {}
10
11 int sumRange(int left, int right) {
12 int sum = 0;
13 for (int i = left; i <= right; i++) {
14 sum += nums[i];
15 }
16 return sum;
17 }
18};
19
20int main() {
21 vector<int> nums = {-2, 0, 3, -5, 2, -1};
22 NumArray numArray(nums);
23 cout << "sumRange(0, 2): " << numArray.sumRange(0, 2) << endl;
24 cout << "sumRange(2, 5): " << numArray.sumRange(2, 5) << endl;
25 cout << "sumRange(0, 5): " << numArray.sumRange(0, 5) << endl;
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Approach 1: Brute Force — Linear Iteration per Query.
  • Space complexity: O(1) — Space complexity for Approach 1: Brute Force — Linear Iteration per Query.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Better — 2D Matrix Precomputation

Intuition

Precompute the answer for every pair (i, j) into an N x N matrix in the constructor so queries are O(1) table lookups.

Algorithm

  1. Constructor: allocate dp[n][n].
  2. Compute dp[i][j] = dp[i][j-1] + nums[j] for all 0 <= i <= j < n.
  3. sumRange(left, right): return dp[left][right].

Sqrt Decomposition (O(sqrt(N)) per Query)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Sqrt decomposition preprocesses block aggregates
Visual state
Values and pointers at this exact step
pointers
S
-2
0
3
-5
2
-1
0
↑ block0
1
2
3
4
5
Variables at this step
blockSize
3
blocks
[1,-4]
Check / comparison
Block size B = 3. Precompute block sums: Block 0 = -2 + 0 + 3 = 1, Block 1 = -5 + 2 + -1 = -4
Decision / next transition
Blocks = [1, -4].
Why this step matters

Sqrt decomposition preprocesses block aggregates.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// 2D Matrix Precomputation (O(N^2) memory)
6class NumArray {
7 vector<vector<int>> dp;
8public:
9 NumArray(vector<int>& nums) {
10 int n = nums.size();
11 dp.assign(n, vector<int>(n, 0));
12 for (int i = 0; i < n; i++) {
13 int sum = 0;
14 for (int j = i; j < n; j++) {
15 sum += nums[j];
16 dp[i][j] = sum;
17 }
18 }
19 }
20
21 int sumRange(int left, int right) {
22 return dp[left][right];
23 }
24};
25
26int main() {
27 vector<int> nums = {-2, 0, 3, -5, 2, -1};
28 NumArray numArray(nums);
29 cout << "sumRange(0, 2): " << numArray.sumRange(0, 2) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Approach 2: Better — 2D Matrix Precomputation.
  • Space complexity: O(N) — Space complexity for Approach 2: Better — 2D Matrix Precomputation.

3. Optimal — 1D Prefix Sum Array (O(1) Query, O(N) Space)

Intuition

Build a prefix sum array of size N + 1 where prefix[i] stores the sum of the first i elements. Answer any query in O(1) via prefix[right + 1] - prefix[left].

Algorithm

  1. Constructor:
  2. Create array prefix of size nums.length + 1 initialized to 0.
  3. For i = 0 to nums.length - 1:
  4. prefix[i + 1] = prefix[i] + nums[i].
  5. sumRange(left, right):
  6. Return prefix[right + 1] - prefix[left].

Prefix Sum Array (O(1) Time per Query)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Prefix array stores immutable cumulative sums
Visual state
Values and pointers at this exact step
pointers
S
0
-2
-2
1
-4
-2
-3
0
↑ P
1
2
3
4
5
6
Variables at this step
prefixBuilt
true
Check / comparison
Precompute 1-based prefix sums P: [0, -2, -2, 1, -4, -2, -3]
Decision / next transition
P[i] = P[i-1] + nums[i-1]. Built in O(N) once in constructor.
Why this step matters

Prefix array stores immutable cumulative sums.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Optimal: 1D Prefix Sum Array (O(N) build, O(1) query, O(N) space)
6class NumArray {
7 vector<int> prefix;
8public:
9 NumArray(vector<int>& nums) {
10 int n = nums.size();
11 prefix.resize(n + 1, 0);
12 for (int i = 0; i < n; i++) {
13 prefix[i + 1] = prefix[i] + nums[i];
14 }
15 }
16
17 int sumRange(int left, int right) {
18 return prefix[right + 1] - prefix[left];
19 }
20};
21
22int main() {
23 vector<int> nums = {-2, 0, 3, -5, 2, -1};
24 NumArray numArray(nums);
25 cout << "sumRange(0, 2): " << numArray.sumRange(0, 2) << endl;
26 cout << "sumRange(2, 5): " << numArray.sumRange(2, 5) << endl;
27 cout << "sumRange(0, 5): " << numArray.sumRange(0, 5) << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Approach 3: Optimal — 1D Prefix Sum Array (O(1) Query, O(N) Space).
  • Space complexity: O(1) — Space complexity for Approach 3: Optimal — 1D Prefix Sum Array (O(1) Query, O(N) Space).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Scan per QueryO(1) build, O(N) queryO(1) auxiliaryZero precomputation, instant constructor.Baseline only.
2.2D Precomputed MatrixO(N²) build, O(1) queryO(N²)O(1) table lookup.Sub-optimal due to excessive space.
3.1D Prefix Sum ArrayOptimalO(N) build, O(1) queryO(N)Optimal O(1) query time, minimal linear O(N) space, elegant formula.Optimal gold standard.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Query Entire Array (left = 0, right = n - 1) — Input: nums = [1, 2, 3], sumRange(0, 2), Expected: 6 — prefix[3] - prefix[0] = 6 - 0 = 6.
  • Single Element Query (left == right) — Input: nums = [4, 8, 12], sumRange(1, 1), Expected: 8 — prefix[2] - prefix[1] = 12 - 4 = 8.
  • Negative Numbers and Zeros — Input: nums = [-2, 0, 3, -5], sumRange(0, 3), Expected: -4 — Prefix sums handle negative values without special sign handling.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Design Discussion — Highlight constructor vs query trade-offs: 'We do O(N) work once in the constructor so that every subsequent query is O(1) time.'
  2. Mention 1-based size N+1 trick — Explain why prefix has size N + 1: 'It cleanly guards against left = 0 edge cases without extra branching.'
  3. Follow-up — Be ready for follow-up: 'What if values are updated dynamically?' (Fenwick Tree / Segment Tree in O(log N) per update and query).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Range Sum Query - Immutable?

2.Why is the brute force approach suboptimal for large inputs in Range Sum Query - Immutable?

3.Which data structure or technique enables the optimal solution for Range Sum Query - Immutable?

Back to DSA Sheet