#303 Range Sum Query - Immutable

frequently reported atInfosys Meta Amazon Bloomberg Google Microsoft

the problem

In plain words

Design a class built from an integer array that answers many sumRange(left, right) queries: the sum of elements between the two indices, inclusive. The array never changes.

in nums = [-2,0,3,-5,2,-1]; sumRange(0,2), sumRange(2,5), sumRange(0,5)

out 1, -1, -3

1 ≤ n ≤ 10⁴
-10⁵ ≤ nums[i] ≤ 10⁵
Up to 10⁴ calls to sumRange

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternPrefix sums

The array is immutable and queried many times, so pay O(n) once in the constructor and make each query O(1).

solutions

From brute force to optimal

Store the array; add up nums[left..right] per query.

sumRange: for i in left..right, sum += nums[i].

timeO(n) per query

A range can cover the whole array; q queries cost O(n·q).

spaceO(1) extra

Just a reference to the array.

java

1/** LeetCode names this class NumArray. */2class NumArrayLoop {3    private final int[] nums;4 5    public NumArrayLoop(int[] nums) {6        this.nums = nums;7    }8 9    public int sumRange(int left, int right) {10        int sum = 0;11        for (int i = left; i <= right; i++) sum += nums[i]; // O(n) on every call12        return sum;13    }14}

prefix[i] = sum of the first i numbers; a range is a difference of two prefixes.

Constructor: prefix[i+1] = prefix[i] + nums[i].
sumRange: prefix[right+1] − prefix[left].

timeO(n) build, O(1) per query

One pass to build, one subtraction per query.

spaceO(n)

n + 1 prefix values.

java

1class NumArray {2    private final int[] prefix; // prefix[i] = sum of the first i numbers3 4    public NumArray(int[] nums) {5        prefix = new int[nums.length + 1];6        for (int i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i]; // O(n) once7    }8 9    public int sumRange(int left, int right) {10        return prefix[right + 1] - prefix[left]; // O(1) per call11    }12}

sim

Build and query

loading simulation…

javajava.util.*

1class PrefixSum {2    private final long[] prefix; // prefix[i] = nums[0] + ... + nums[i-1]3 4    PrefixSum(int[] nums) {5        prefix = new long[nums.length + 1]; // prefix[0] = 0: the empty sum6        for (int i = 0; i < nums.length; i++) {7            prefix[i + 1] = prefix[i] + nums[i];8        }9    }10 11    /** Sum of nums[left..right], inclusive, in O(1). */12    long rangeSum(int left, int right) {13        return prefix[right + 1] - prefix[left];14    }15}

in the room

How to say it in the interview

talk track

Ask how many queries to expect: that decides whether precomputing is worth it.
Mention the n + 1 sizing and why prefix[0] = 0.
Mention overflow: the worst sum here is 10⁴ × 10⁵ = 10⁹, which fits in int, but say you'd use long for larger inputs.

traps

Off-by-one: it's prefix[right + 1] − prefix[left], not prefix[right] − prefix[left].

what they ask next

Follow-ups

What if elements can be updated (LC 307)?

A prefix array would need O(n) per update. Use a Fenwick tree or segment tree: O(log n) for both update and query.

2D version (LC 304)?

2D prefix sums: P[r+1][c+1] = P[r][c+1] + P[r+1][c] − P[r][c] + m[r][c]; a query is inclusion–exclusion of four corners.

before you submit

Edge cases to test

left == right → a single element.
left = 0 → prefix[0] = 0 handles it with no special case.
Negative numbers — prefix sums go up and down, and that's fine.

practise next