Why do so many array interview questions reduce to the same three lines of math?
Because once you understand prefix sums, you can turn a whole class of “sum of this subarray” and “how many times does this condition happen” problems into mechanical O(1) queries after a single O(n) pass over the array.
In this post we’ll build the idea from scratch, then layer on:
Deriving the prefix sum formula from first principles
Cumulative frequency maps (prefix sums over counts, not values)
2D prefix sums for matrices
Running sum vs. separate prefix array trade‑offs
A simple Big O proof that you can reuse in interviews
I’ll include TypeScript, Java, C#, and Python snippets so you can see the pattern in your favorite language.
1. Deriving prefix sums from first principles
Imagine the most basic question:
Given an array
nums, answer many queries of the form: “What is the sum ofnums[l…r]?”
Brute force says: for each query, loop from l to r and add. That’s O(length of range) per query, which becomes O(n * q) for q queries.
The prefix trick is: do the work once, then reuse it.
Let prefix[i] be the sum of the first i elements:
Then the sum of a subarray nums[l…r] is:
Why? Because prefix[r] includes everything from 0…r, and prefix[l-1] includes everything from 0…l-1, so subtracting cancels out the prefix and leaves l…r.
Corner case: when l = 0, we define
Building the prefix array
All four languages share the same core loop: “current prefix equals previous prefix plus current element.”
TypeScript
function buildPrefix(nums: number[]): number[] {
const prefix = new Array(nums.length);
let running = 0;
for (let i = 0; i < nums.length; i++) {
running += nums[i];
prefix[i] = running;
}
return prefix;
}
function rangeSum(prefix: number[], l: number, r: number): number {
if (l === 0) return prefix[r];
return prefix[r] - prefix[l - 1];
}Java
int[] buildPrefix(int[] nums) {
int n = nums.length;
int[] prefix = new int[n];
int running = 0;
for (int i = 0; i < n; i++) {
running += nums[i];
prefix[i] = running;
}
return prefix;
}
int rangeSum(int[] prefix, int l, int r) {
if (l == 0) return prefix[r];
return prefix[r] - prefix[l - 1];
}C#
int[] BuildPrefix(int[] nums) {
int n = nums.Length;
int[] prefix = new int[n];
int running = 0;
for (int i = 0; i < n; i++) {
running += nums[i];
prefix[i] = running;
}
return prefix;
}
int RangeSum(int[] prefix, int l, int r) {
if (l == 0) return prefix[r];
return prefix[r] - prefix[l - 1];
}Python
from typing import List
def build_prefix(nums: List[int]) -> List[int]:
prefix = []
running = 0
for x in nums:
running += x
prefix.append(running)
return prefix
def range_sum(prefix: List[int], l: int, r: int) -> int:
if l == 0:
return prefix[r]
return prefix[r] - prefix[l - 1]Once students internalize “subarray sum = difference of two prefix sums,” a large set of LeetCode medium problems becomes immediately solvable.
The rest of the post is for paid subscribers and covers cumulative frequency maps, 2D prefix sums, running sums vs. separate prefix arrays, and a Big O proof of preprocessing and range query costs.
Includes code samples in Java, Python, C# and TypeScript.
