LeetCodeRange Sum Query - Immutable
Prefix Sum
Asked at 7 companies
4 recent
- Meta
- Amazon
- Microsoft
- Infosys
- Bloomberg
- tcs
Community-reported · source · updated 2026-10-08. ● asked in the last 6 months.
Go step by step: try it yourself before the video and the visual. Progress saves on this device.
0 / 110 pointsSolved (Easy) 0/20Reviews 0/50Mastered 0/25Practice steps 0/15
Step 1
Know these before you start
Practise each one here, or tick what you already know
Concept videoStep 2
Try it on paper
5–10 minutes, no code yet
In the wild · Analytics dashboards: “Sales between March 3 and March 17” is one subtraction of two running totals, so charts answer any date range instantly instead of re-adding every day.
About this problem
Running totals turn any range sum into one subtraction, and a hash map of them counts subarrays in one pass.
Read the full statement and examples on LeetCode, try it for 20–30 minutes, then come back for the walkthrough.
Examples
Full statement on LeetCode ↗Example calls
- obj = NumArray([-2, 0, 3, -5, 2, -1])
- obj.sumRange(0, 2) → 1
- obj.sumRange(2, 5) → -1
- obj.sumRange(0, 5) → -3
Code it on LeetCode
This one needs setup the editor here can't do yet (a class you build, linked nodes, or a helper LeetCode provides), so solve it on LeetCode, with its own tests. Then tick My code passed below, and it joins your reviews. With your LeetCode account linked, that happens on its own.
Solve on LeetCode Step 6
Get it accepted
All test cases pass
Step 7
Review it so it sticks
Re-solve from memory after
The step that matters most: without reviews most of a solved problem fades within weeks. Three short re-solves, each just as you start to forget, are what make it yours.
Your notes
Three lines in your own words. They come back with this problem's reviews, so you can check yourself after recalling the solution.
Solve it yourself before you look
Reading the solution first feels like progress, but it makes the next similar problem — and the interview version — much harder, because you skipped the part where you figure it out. Give it an honest 20–30 minutes. Stuck? Re-read the pattern, watch the concept video, or try the brute force first.
Hidden: optimal solution
Solution code
Optimal solutionBuild prefix[i] = sum of the first i numbers once. Then the sum of nums[left..right] is prefix[right + 1] − prefix[left], per query.
class NumArray:
def __init__(self, nums: List[int]):
self.prefix = [0]
for x in nums:
self.prefix.append(self.prefix[-1] + x)
def sumRange(self, left: int, right: int) -> int:
return self.prefix[right + 1] - self.prefix[left]Reference solution, tested in Python, Java and C++.
Other ways to solve it
- Community solutions on LeetCode ↗ for many more versions, in many languages. Read them after you've solved it.