Answer a Range Sum Query on an Array

Easy10–15 min

Topics

ArrayPrefix Sum

Companies

AmazonMicrosoftGoogleBloomberg

Given an array of integers nums, answer queries of the form: what is the sum of the elements between index left and index right, inclusive? Summing the range directly answers one query correctly, but it re-walks the same ground every time. In a system where the array stays fixed and the same range gets queried over and over, that's wasted work — a prefix sum array, built once, turns every future range query into a single subtraction.

Test Case 1:

Input:nums = [-2, 0, 3, -5, 2, -1], left = 0, right = 2

Output:1

Explanation:-2 + 0 + 3 = 1.

Test Case 2:

Input:nums = [-2, 0, 3, -5, 2, -1], left = 2, right = 5

Output:-1

Explanation:3 + -5 + 2 + -1 = -1.

Test Case 3:

Input:nums = [-2, 0, 3, -5, 2, -1], left = 0, right = 5

Output:-3

Explanation:The whole array sums to -3.

Constraints

◆1 ≤ nums.length ≤ 10⁴
◆-10⁵ ≤ nums[i] ≤ 10⁵
◆0 ≤ left ≤ right < nums.length

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 3-8 integersleft index — 0 to nums.length - 1right index — left to nums.length - 1

1	class Solution {
2	public int rangeSum(int[] nums, int left, int right) {
3	int[] prefix = new int[nums.length + 1];
4	for (int i = 0; i < nums.length; i++) {
5	prefix[i + 1] = prefix[i] + nums[i];
6	}
7	return prefix[right + 1] - prefix[left];
8	}
9	}
10

Array

-2

-5

-1

↑i

Array

-2

Variables

i0

prefix[1]-2

prefix[1] = prefix[0] + nums[0] = 0 + -2 = -2

CALCULATE

Extend the prefix array: prefix[1] = -2, the sum of nums[0..0].

Step 1 / 7

Approach & Solutions

Brute Force

Brute

Walk from left to right, adding each element into a running sum. Correct, but every query re-walks its whole range from scratch — if this array were queried many times, that repeated work adds up fast.

TimeO(n) per query

SpaceO(1)

Java

Try it out

class Solution {
    public int rangeSum(int[] nums, int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum += nums[i];
        }
        return sum;
    }
}

Optimal — Prefix Sum

Optimal

Build a prefix array where prefix[i] holds the sum of every element before index i (so prefix[0] = 0, prefix[1] = nums[0], and so on). Once that's built, the sum of any range [left, right] is just prefix[right + 1] - prefix[left] — one subtraction, no matter how wide the range is. In a real system that answers this query repeatedly against the same array, you'd build the prefix array once and reuse it for every query, turning each one into O(1) instead of O(range). This version rebuilds it on every call to keep the function pure and self-contained, but the underlying trick — and the reason it's fast when reused — is exactly the same.

TimeO(n) to build, O(1) per query

SpaceO(n)