Stage 1 · Code
Arrays & Hashing
Prefix Sum
Precompute cumulative sums to answer any range query in O(1) — one of the most reusable interview tricks.
8 min readLeetCode Patterns for InterviewsCode
The Pattern
A prefix sum array pre[i] stores the sum of nums[0..i-1]. Any contiguous subarray sum nums[l..r] is then pre[r+1] - pre[l] — O(1) after O(n) preprocessing.
Prefix sum — range query [1..3] = 9
nums[]
1
2
3
4
5
0
1
2
3
4
prefix[] (prefix[i] = sum of nums[0..i-1])
0
1
3
6
10
15
0
1
2
3
4
5
sum[1..3] = prefix[4] − prefix[1] = 9
Goprefix-sum-template.go
25 linesLn 1, Col 1Go
pre[0]=0 acts as a sentinel so pre[r+1]-pre[l] works even when l=0 without special casing.
Template
The prefix sum mental model
Think of pre[i] as the 'running total through position i'. A range [l,r] is (total through r+1) minus (total through l). Drawing the number line with prefix values annotated removes all off-by-one confusion.
Problems
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.