Problem 5.1 · Prefix SumEasy

Range Sum Queries

What it teaches: Precompute once, answer many: O(n + q) instead of O(n · q).

Practise it on judges as “Range Sum Query - Immutable”.

The problem

Given an integer array nums and a list of queries, where each query is [left, right], return an array with the sum of nums[left..right] (inclusive) for each query.

Example 1

Input: nums = [-2, 0, 3, -5, 2, -1], queries = [[0, 2], [2, 5], [0, 5]]
Output: [1, -1, -3]

Constraints

1 ≤ nums.length ≤ 10⁴
1 ≤ queries.length ≤ 10⁴
−10⁵ ≤ nums[i] ≤ 10⁵

Pattern clues in the wording

→ Many range-sum queries on an array that doesn't change
→ q × n would be 10⁸ steps

These clues point to Prefix Sum: Store running totals so the sum of any range is one subtraction: prefix[r + 1] - prefix[l].

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int[] rangeSums(int[] nums, int[][] queries) {
        int[] prefix = new int[nums.length + 1];
        int[] out = new int[queries.length];
        return out;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [-2,0,3,-5,2,-1] queries = [[0,2],[2,5],[0,5]]	[1,-1,-3]
2	nums = [5] queries = [[0,0]]	[5]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Loop per query · O(n · q)2. Optimal: prefix sums · O(n + q)

Loop per query

Time O(n · q) Space O(1) extra

For each query, add up the elements in its range.

Approach 1

class Solution {
    public int[] rangeSums(int[] nums, int[][] queries) {
        int[] out = new int[queries.length];
        for (int q = 0; q < queries.length; q++)
            for (int i = queries[q][0]; i <= queries[q][1]; i++) out[q] += nums[i];
        return out;
    }
}

Verdict: Up to 10⁸ additions: borderline. The repeated work is re-adding the same elements for overlapping queries.

Optimal: prefix sums

Time O(n + q) Space O(n)

Build prefix of length n + 1, then answer each query with prefix[right + 1] − prefix[left].

Approach 2

class Solution {
    public int[] rangeSums(int[] nums, int[][] queries) {
        int[] prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
        int[] out = new int[queries.length];
        for (int q = 0; q < queries.length; q++) out[q] = prefix[queries[q][1] + 1] - prefix[queries[q][0]];
        return out;
    }
}

Verdict: Each element is added once, and each query is O(1).

Before you submit

Edge cases and common mistakes

Test these inputs

Query of a single element
Query of the whole array
Negative values

Mistakes people make

Using prefix[right] − prefix[left] (drops the right element).

Interview

Follow-up questions

What if nums can change between queries?

Command Palette