Range Sum Query - Immutable solution and explanation
Infosys
Google
TCS
9 more videos on this problem
Range Sum Query Immutable - Leetcode 303 - PythonNeetCodeIO · 7:42 · 44K views
Leetcode Range Sum Query - Immutable || Intuition + Example + CodeCode with Alisha · 11:00 · 12K views
Range Sum Query - Immutable | Leetcode 303 | Live coding session 🔥🔥🔥 | Prefix SumCoding Decoded · 6:39 · 7K views
LeetCode 303 Range Sum Query - Immutable | Prefix Sum | Beginner Friendly ExplanationCode Harmony · 18:13 · 5K views
Leetcode - 303 Range Sum Query - Immutable (Easy) in Java,PythonCoding Sensei · 9:56 · 2K views
Range Sum Query - Immutable - LeetCode 303 - Coding Interview QuestionsOne Code Man · 4:20 · 2K views
Leetcode 303 Range Sum Query - Immutable (Java)TheAnalyticGuy · 10:53 · 2K views
303. Range Sum Query - Immutable (Leetcode Easy)Programming Live with Larry · 5:52 · 594 views
LeetCode 303 | Range Sum Query - Immutable | Brute Force Approach in Java | CodeZen by SharadCodeZen by Sharad · 13:30 · 419 views
303 LeetCode | Range Sum Query - Immutable | DSA with JavaScriptPeer Programming · 15:10 · 235 views
The problem
Given an integer array nums, handle multiple queries of the following type:
- Calculate the sum of the elements of
numsbetween indicesleftandrightinclusive whereleft <= right.
Implement the NumArray class:
NumArray(int[] nums)Initializes the object with the integer arraynums.int sumRange(int left, int right)Returns the sum of the elements ofnumsbetween indicesleftandrightinclusive (i.e.nums[left] + nums[left + 1] + ... + nums[right]).
Example 1:
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); // return (-2) + 0 + 3 = 1 numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1 numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3
Constraints:
1 <= nums.length <= 104-105 <= nums[i] <= 1050 <= left <= right < nums.length- At most
104calls will be made tosumRange.
Approach overview
Problem Overview: You receive an integer array and must answer multiple queries asking for the sum of elements between two indices left and right (inclusive). The array never changes after initialization, so the challenge is designing a structure that answers range sum queries efficiently.
Approach 1: Brute Force Iteration (O(n) per query, O(1) space)
The simplest method recomputes the sum for every query. Iterate from index left to right and accumulate the values. Each query scans a portion of the array, so the time complexity is O(n) in the worst case per query. This approach requires no preprocessing and only constant extra space, but performance quickly degrades when many queries are executed. It mainly serves as a baseline that demonstrates why preprocessing is useful.
Approach 2: Prefix Sum Array (O(n) preprocessing, O(1) query, O(n) space)
The optimal solution precomputes cumulative sums using a prefix sum array. During initialization, build an array where prefix[i] stores the sum of elements from index 0 through i. Once built, any query can be answered using subtraction: sum(left, right) = prefix[right] - prefix[left - 1] (with a small edge-case check when left = 0). Preprocessing runs once in O(n), and every query becomes a constant-time lookup. This works well because the underlying array never changes.
Approach 3: Segment Tree (O(n) build, O(log n) query, O(n) space)
A segment tree stores range sums in a balanced tree structure where each node represents the sum of a segment of the array. Queries traverse only the nodes that overlap with the requested range, producing a time complexity of O(log n). This structure is powerful when the array supports updates because modifications can also be handled in O(log n). In this specific problem the array is immutable, so the segment tree is more complex than necessary compared to prefix sums.
Recommended for interviews: Prefix sum is the expected solution. Interviewers want to see that you recognize the array never changes and trade a one-time preprocessing step for constant-time queries. Mentioning the brute force approach first shows you understand the baseline, while implementing prefix sums demonstrates algorithmic optimization and familiarity with a common pattern used in many range query problems.
Approach 1: Prefix Sum Array
The key idea in this approach is to use a prefix sum array. We precompute cumulative sums such that each element at index i in this prefix array contains the sum of all elements in the nums array from index 0 to i. The sum of a subarray can then be computed in constant time using the relation: sumRange(left, right) = prefixSum[right] - prefixSum[left-1]. This pre-computation allows each query to be answered in O(1) time after O(n) pre-computation.
class NumArray:
def __init__(self, nums: List[int]):
self.prefix_sums = [0]
for num in nums:
self.prefix_sums.append(self.prefix_sums[-1] + num)
def sumRange(self, left: int, right: int) -> int:
return self.prefix_sums[right + 1] - self.prefix_sums[left]class NumArray {
private int[] prefixSums;
public NumArray(int[] nums) {
prefixSums = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefixSums[i + 1] = prefixSums[i] + nums[i];
}
}
public int sumRange(int left, int right) {
return prefixSums[right + 1] - prefixSums[left];
}
}#include <vector>
class NumArray {
public:
std::vector<int> prefixSums;
NumArray(std::vector<int>& nums) {
prefixSums.resize(nums.size() + 1);
prefixSums[0] = 0;
for (int i = 0; i < nums.size(); ++i) {
prefixSums[i + 1] = prefixSums[i] + nums[i];
}
}
int sumRange(int left, int right) {
return prefixSums[right + 1] - prefixSums[left];
}
};class NumArray {
constructor(nums) {
this.prefixSums = [0];
for (let num of nums) {
this.prefixSums.push(this.prefixSums[this.prefixSums.length - 1] + num);
}
}
sumRange(left, right) {
return this.prefixSums[right + 1] - this.prefixSums[left];
}
}#include <stdlib.h>
typedef struct {
int* prefixSums;
int size;
} NumArray;
NumArray* numArrayCreate(int* nums, int numsSize) {
NumArray* obj = (NumArray*)malloc(sizeof(NumArray));
obj->prefixSums = (int*)malloc((numsSize + 1) * sizeof(int));
obj->size = numsSize;
obj->prefixSums[0] = 0; // Initialize prefix sum for index 0
for (int i = 0; i < numsSize; ++i) {
obj->prefixSums[i + 1] = obj->prefixSums[i] + nums[i];
}
return obj;
}
int numArraySumRange(NumArray* obj, int left, int right) {
return obj->prefixSums[right + 1] - obj->prefixSums[left];
}
void numArrayFree(NumArray* obj) {
free(obj->prefixSums);
free(obj);
}public class NumArray {
private int[] prefixSums;
public NumArray(int[] nums) {
prefixSums = new int[nums.Length + 1];
for (int i = 0; i < nums.Length; i++) {
prefixSums[i + 1] = prefixSums[i] + nums[i];
}
}
public int SumRange(int left, int right) {
return prefixSums[right + 1] - prefixSums[left];
}
}In this Python implementation, a list called prefix_sums is initialized to hold cumulative sums. During each call of sumRange, the range sum is returned using precomputed values.
Time Complexity: O(n) for creating prefix sums, O(1) per sumRange call.
Space Complexity: O(n) for storing prefix sums.
Approach 2: Segment Tree
A Segment Tree is a data structure that allows efficient range query and update operations. It is particularly useful in scenarios where there are multiple queries of the dynamic array that could change over time. For sumRange queries, the segment tree helps to retrieve the sum in logarithmic time, and it can be further extended to handle updates if needed.
class NumArray:
def __init__(self, nums: List[int]):
self.n = len(nums)
self.segment_tree = [0] * (4 * self.n)
self.build_tree(nums, 0, self.n - 1, 0)
def build_tree(self, nums, start, end, node):
if start == end:
self.segment_tree[node] = nums[start]
else:
mid = start + (end - start) // 2
self.build_tree(nums, start, mid, 2 * node + 1)
self.build_tree(nums, mid + 1, end, 2 * node + 2)
self.segment_tree[node] = self.segment_tree[2 * node + 1] + self.segment_tree[2 * node + 2]
def sumRange(self, left: int, right: int) -> int:
return self.range_sum(0, self.n - 1, 0, left, right)
def range_sum(self, start, end, node, left, right):
if right < start or left > end:
return 0
if left <= start and end <= right:
return self.segment_tree[node]
mid = start + (end - start) // 2
sum_left = self.range_sum(start, mid, 2 * node + 1, left, right)
sum_right = self.range_sum(mid + 1, end, 2 * node + 2, left, right)
return sum_left + sum_rightclass NumArray {
private int[] segmentTree;
private int n;
public NumArray(int[] nums) {
n = nums.length;
segmentTree = new int[4 * n];
buildTree(nums, 0, n - 1, 0);
}
private void buildTree(int[] nums, int start, int end, int node) {
if (start == end) {
segmentTree[node] = nums[start];
} else {
int mid = start + (end - start) / 2;
buildTree(nums, start, mid, 2 * node + 1);
buildTree(nums, mid + 1, end, 2 * node + 2);
segmentTree[node] = segmentTree[2 * node + 1] + segmentTree[2 * node + 2];
}
}
public int sumRange(int left, int right) {
return rangeSum(0, n - 1, 0, left, right);
}
private int rangeSum(int start, int end, int node, int left, int right) {
if (right < start || end < left) return 0;
if (left <= start && end <= right) return segmentTree[node];
int mid = start + (end - start) / 2;
return rangeSum(start, mid, 2 * node + 1, left, right) +
rangeSum(mid + 1, end, 2 * node + 2, left, right);
}
}#include <vector>
class NumArray {
public:
std::vector<int> segmentTree;
int n;
NumArray(std::vector<int>& nums) {
n = nums.size();
segmentTree.resize(4 * n);
buildTree(nums, 0, n - 1, 0);
}
void buildTree(std::vector<int>& nums, int start, int end, int node) {
if (start == end) {
segmentTree[node] = nums[start];
} else {
int mid = start + (end - start) / 2;
buildTree(nums, start, mid, 2 * node + 1);
buildTree(nums, mid + 1, end, 2 * node + 2);
segmentTree[node] = segmentTree[2 * node + 1] + segmentTree[2 * node + 2];
}
}
int sumRange(int left, int right) {
return rangeSum(0, n - 1, 0, left, right);
}
int rangeSum(int start, int end, int node, int left, int right) {
if (right < start || left > end) return 0;
if (left <= start && end <= right) return segmentTree[node];
int mid = start + (end - start) / 2;
return rangeSum(start, mid, 2 * node + 1, left, right) +
rangeSum(mid + 1, end, 2 * node + 2, left, right);
}
};class NumArray {
constructor(nums) {
this.n = nums.length;
this.segmentTree = new Array(4 * this.n).fill(0);
this.buildTree(nums, 0, this.n - 1, 0);
}
buildTree(nums, start, end, node) {
if (start === end) {
this.segmentTree[node] = nums[start];
} else {
const mid = start + Math.floor((end - start) / 2);
this.buildTree(nums, start, mid, 2 * node + 1);
this.buildTree(nums, mid + 1, end, 2 * node + 2);
this.segmentTree[node] = this.segmentTree[2 * node + 1] + this.segmentTree[2 * node + 2];
}
}
sumRange(left, right) {
return this.rangeSum(0, this.n - 1, 0, left, right);
}
rangeSum(start, end, node, left, right) {
if (right < start || left > end) return 0;
if (left <= start && end <= right) return this.segmentTree[node];
const mid = start + Math.floor((end - start) / 2);
return this.rangeSum(start, mid, 2 * node + 1, left, right) +
this.rangeSum(mid + 1, end, 2 * node + 2, left, right);
}
}#include <stdlib.h>
typedef struct {
int* segmentTree;
int n;
} NumArray;
void buildTree(int start, int end, int node, NumArray* obj, int* nums) {
if (start == end) {
obj->segmentTree[node] = nums[start];
} else {
int mid = start + (end - start) / 2;
int leftChild = node * 2 + 1;
int rightChild = node * 2 + 2;
buildTree(start, mid, leftChild, obj, nums);
buildTree(mid + 1, end, rightChild, obj, nums);
obj->segmentTree[node] = obj->segmentTree[leftChild] + obj->segmentTree[rightChild];
}
}
int queryTree(int start, int end, int node, int left, int right, NumArray* obj) {
if (right < start || end < left) {
return 0;
}
if (left <= start && end <= right) {
return obj->segmentTree[node];
}
int mid = start + (end - start) / 2;
int leftChild = node * 2 + 1;
int rightChild = node * 2 + 2;
int sumLeft = queryTree(start, mid, leftChild, left, right, obj);
int sumRight = queryTree(mid + 1, end, rightChild, left, right, obj);
return sumLeft + sumRight;
}
NumArray* numArrayCreate(int* nums, int numsSize) {
NumArray* obj = (NumArray*)malloc(sizeof(NumArray));
obj->n = numsSize;
obj->segmentTree = (int*)malloc(4 * numsSize * sizeof(int));
buildTree(0, numsSize - 1, 0, obj, nums);
return obj;
}
int numArraySumRange(NumArray* obj, int left, int right) {
return queryTree(0, obj->n - 1, 0, left, right, obj);
}
void numArrayFree(NumArray* obj) {
free(obj->segmentTree);
free(obj);
}public class NumArray {
private int[] segmentTree;
private int n;
public NumArray(int[] nums) {
n = nums.Length;
segmentTree = new int[4 * n];
BuildTree(nums, 0, n - 1, 0);
}
private void BuildTree(int[] nums, int start, int end, int node) {
if (start == end) {
segmentTree[node] = nums[start];
} else {
int mid = (start + end) / 2;
BuildTree(nums, start, mid, 2 * node + 1);
BuildTree(nums, mid + 1, end, 2 * node + 2);
segmentTree[node] = segmentTree[2 * node + 1] + segmentTree[2 * node + 2];
}
}
public int SumRange(int left, int right) {
return RangeSum(0, n - 1, 0, left, right);
}
private int RangeSum(int start, int end, int node, int left, int right) {
if (right < start || end < left) return 0;
if (left <= start && end <= right) return segmentTree[node];
int mid = (start + end) / 2;
return RangeSum(start, mid, 2 * node + 1, left, right) +
RangeSum(mid + 1, end, 2 * node + 2, left, right);
}
}The Python version implements a segment tree where nodes accumulate over complementary segments of the array, calculating sums that enable sumRange to work efficiently.
Time Complexity: O(n) set up, O(log n) queries.
Space Complexity: O(n) for segment retention.
Approach 3: Prefix Sum
We create a prefix sum array s of length n + 1, where s[i] represents the prefix sum of the first i elements, that is, s[i] = sum_{j=0}^{i-1} nums[j]. Therefore, the sum of the elements between the indices [left, right] can be expressed as s[right + 1] - s[left].
The time complexity for initializing the prefix sum array s is O(n), and the time complexity for querying is O(1). The space complexity is O(n).
class NumArray {
private s: number[];
constructor(nums: number[]) {
const n = nums.length;
this.s = Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
this.s[i + 1] = this.s[i] + nums[i];
}
}
sumRange(left: number, right: number): number {
return this.s[right + 1] - this.s[left];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* var obj = new NumArray(nums)
* var param_1 = obj.sumRange(left,right)
*/type NumArray struct {
s []int
}
func Constructor(nums []int) NumArray {
n := len(nums)
s := make([]int, n+1)
for i, v := range nums {
s[i+1] = s[i] + v
}
return NumArray{s}
}
func (this *NumArray) SumRange(left int, right int) int {
return this.s[right+1] - this.s[left]
}
/**
* Your NumArray object will be instantiated and called as such:
* obj := Constructor(nums);
* param_1 := obj.SumRange(left,right);
*/class NumArray(nums: IntArray) {
private val prefix_sums: IntArray
init {
val nums_size = nums.size
this.prefix_sums = IntArray(nums_size + 1)
for (i in 0..<nums_size) {
this.prefix_sums[i + 1] = this.prefix_sums[i] + nums[i]
}
}
fun sumRange(left: Int, right: Int): Int = this.prefix_sums[right + 1] - this.prefix_sums[left]
}
/**
* Your NumArray object will be instantiated and called as such: var obj = NumArray(nums) var
* param_1 = obj.sumRange(left,right)
*/struct NumArray {
s: Vec<i32>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl NumArray {
fn new(mut nums: Vec<i32>) -> Self {
let n = nums.len();
let mut s = vec![0; n + 1];
for i in 0..n {
s[i + 1] = s[i] + nums[i];
}
Self { s }
}
fn sum_range(&self, left: i32, right: i32) -> i32 {
self.s[(right + 1) as usize] - self.s[left as usize]
}
}class NumArray {
/**
* @param Integer[] $nums
*/
function __construct($nums) {
$this->s = [0];
foreach ($nums as $x) {
$this->s[] = $this->s[count($this->s) - 1] + $x;
}
}
/**
* @param Integer $left
* @param Integer $right
* @return Integer
*/
function sumRange($left, $right) {
return $this->s[$right + 1] - $this->s[$left];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* $obj = NumArray($nums);
* $ret_1 = $obj->sumRange($left, $right);
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum Array | Time Complexity: O(n) for creating prefix sums, O(1) per sumRange call. |
| Segment Tree | Time Complexity: O(n) set up, O(log n) queries. |
| Prefix Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Iteration | O(n) per query | O(1) | Small input sizes or very few queries |
| Prefix Sum Array | O(n) build, O(1) query | O(n) | Best choice when the array is immutable and queries are frequent |
| Segment Tree | O(n) build, O(log n) query | O(n) | Useful if range queries and updates both need to be supported |
Frequently asked questions
Is Range Sum Query - Immutable easy or hard?
Range Sum Query - Immutable is categorized as an Easy problem on LeetCode with an acceptance rate above 70%. The main concept is understanding prefix sums and recognizing when preprocessing can reduce repeated work in multiple queries.
How to solve Range Sum Query - Immutable in O(n)?
Build a prefix sum array where each index stores the cumulative sum up to that position. After this O(n) preprocessing step, compute any range sum in constant time using subtraction of prefix values. This converts repeated summation work into simple arithmetic lookups.
Range Sum Query - Immutable Python or Java solution?
Most implementations create a prefix array during object initialization and compute sums in the sumRange function. Python, Java, C++, and JavaScript solutions all follow the same logic: preprocess cumulative sums once and answer queries with constant-time subtraction.
What is the best approach for Range Sum Query - Immutable?
The prefix sum array approach is the most efficient for this problem. Precompute cumulative sums in O(n) time, then answer each range query in O(1) using prefix[right] - prefix[left-1]. Because the array never changes, prefix sums eliminate repeated scanning of elements.
What data structure is used in Range Sum Query - Immutable?
The most common structure is a prefix sum array that stores cumulative totals for fast lookups. A segment tree can also be used for range queries, though it is typically unnecessary when the array is immutable and updates are not required.
What is the time complexity of Range Sum Query - Immutable?
Using the optimal prefix sum solution, preprocessing takes O(n) time and each query runs in O(1). The brute force method requires O(n) time per query, while a segment tree answers queries in O(log n) after O(n) preprocessing.
Is Range Sum Query - Immutable asked at Google, Amazon, or Meta?
Range query problems using prefix sums appear frequently in interviews at companies like Amazon, Google, and Meta. The exact problem may vary, but the prefix sum technique is a common pattern used in array and subarray sum questions.