2D prefix sums
Store the total of every top-left rectangle of a grid, so the sum of any rectangle takes four lookups.
O(rows * cols) to build, O(1) per rectangleSpace O(rows * cols)5 practice problemsStep-through pictureThe idea
A 2D prefix sum does for a grid what a prefix sum does for a list. It stores, for every cell, the total of the rectangle from the top-left corner of the grid down to that cell. Building it takes one pass over the grid.
After that, the sum of any rectangle is found with four numbers: the big rectangle up to its bottom-right corner, minus the strip above it, minus the strip to its left, plus the top-left corner that was taken away twice.
Like the 1D version, prefix has one extra row and one extra column of zeros, so rectangles that touch the top or left edge need no special case.
An everyday example
Counting seats in a theater section
A theater sells seats in a grid. A board keeps, for every seat, how many tickets are sold in the block from the front-left corner to that seat. To find how many are sold in a middle section, the manager takes the block up to the section's back-right seat, removes the block in front of the section and the block to its left, and adds back the front-left block, because it was removed twice.
| In the example | In the code |
|---|---|
| Tickets sold up to a seat, from the front-left corner | prefix[r + 1][c + 1] |
| The block up to the section's back-right seat | prefix[r2 + 1][c2 + 1] |
| The blocks in front of and to the left of the section | prefix[r1][c2 + 1] and prefix[r2 + 1][c1] |
| The front-left block removed twice | + prefix[r1][c1] |
From the slow way to 2d prefix sums
- The obvious way to add up a rectangle of a grid is to visit every cell in it. A big rectangle has up to
rows × colscells, and a task like "the sum around every cell" asks that question once per cell, which multiplies the cost. - A first improvement uses a 1D prefix sum for each row. Then each row's part of the rectangle is one subtraction, and a rectangle costs one subtraction per row. Better, but tall rectangles are still slow.
- Go one step further and store, for every cell, the total of the rectangle from the grid's top-left corner to that cell. Any rectangle is then the big top-left total, minus the part above it, minus the part to its left. Those two parts overlap in the top-left corner, which gets subtracted twice, so add it back once.
- The same add-and-subtract rule fills the table: a cell's total is its value, plus the total above, plus the total to the left, minus their overlap. Filling row by row means those three totals are always ready. Four lookups per rectangle after one pass: that loop is 2D prefix sums.
How it works
- Create
prefixwithrows + 1rows andcols + 1columns of zeros. - For each cell
(r, c), setprefix[r + 1][c + 1]to the cell's value plus the total above it plus the total to its left, minus the total above-left (counted twice). - Now
prefix[r][c]is the sum of all cells in rows0..r - 1and columns0..c - 1. - For a rectangle from
(r1, c1)to(r2, c2), start withprefix[r2 + 1][c2 + 1]. - Subtract
prefix[r1][c2 + 1](everything above) andprefix[r2 + 1][c1](everything to the left). - Add back
prefix[r1][c1], the corner that was subtracted twice.
Watch it run
This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function buildPrefix2D(grid) {const rows = grid.length;const cols = grid[0].length;const prefix = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));for (let r = 0; r < rows; r++) {for (let c = 0; c < cols; c++) {prefix[r + 1][c + 1] = grid[r][c] + prefix[r][c + 1] + prefix[r + 1][c] - prefix[r][c];}}return prefix;}function regionSum(prefix, r1, c1, r2, c2) {return prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1] - prefix[r2 + 1][c1] + prefix[r1][c1];}
How fast it is
| Time | O(rows * cols) to build, O(1) per rectangle |
|---|---|
| Extra memory | O(rows * cols) |
Every cell is filled once with a fixed amount of work. Every rectangle query reads four stored numbers.
- Best case
O(1)Any rectangle question once the table is built: four reads, whether the rectangle is one cell or the whole grid.
- Average case
O(rows × cols)Building the table touches each cell once. After that,
qquestions add onlyqsteps. - Worst case
O(rows × cols)One question on a fresh grid. The build reads every cell, so a single question gains nothing over adding the rectangle directly.
Common mistakes
- Creating rows with
new Array(rows + 1).fill(new Array(cols + 1).fill(0)). Every row is then the same array, so changing one changes all. - Forgetting to add back
prefix[r1][c1], which makes every rectangle not touching the top-left edge too small. - Mixing the shifted indexes: the grid cell
(r, c)is stored atprefix[r + 1][c + 1]. - Not clamping a window to the grid's edges, which reads
undefinedand givesNaN.
When to use it
Look for these clues in a problem:
- Many questions ask for the sum or count inside rectangles of the same grid.
- You need the total of a square or window around every cell (a blur, a neighborhood count).
- The problem searches over many rectangles, such as the largest square with sum at most a limit.
- The grid doesn't change between questions.
Check yourself
Answer each one in your head first, then open it.
In the trace, why is prefix[2][2] 11 even though grid[1][1] is 0?
It holds the whole top-left 2 by 2 block, 2 + 5 + 4 + 0 = 11, not just one cell.
What would prefix[2][2] be if the build forgot - prefix[r][c]?
0 + 7 + 6 = 13, because the cell worth 2 would be counted in both the above part and the left part.
How many numbers does regionSum read, whatever the rectangle's size?
Four: the bottom-right total, the one above the rectangle, the one to its left, and the corner.
Why must the table be filled row by row, left to right?
Each slot needs the slot above it, the slot to its left, and the corner. That order fills all three before they are read.
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingGo further
You don't need these to start practicing. Open one when you want more.
Why it works
The reasoning that makes it always right
Each slot has one meaning: prefix[r][c] is the sum of the grid cells in rows 0 to r - 1 and columns 0 to c - 1. Row 0 and column 0 describe empty rectangles, so they are 0.
To fill prefix[r + 1][c + 1], take prefix[r][c + 1], which covers everything except the last row, and prefix[r + 1][c], which covers everything except the last column. Their sum counts the block prefix[r][c] twice, so subtract it once. The only cell in neither part is grid[r][c], so add it. Filling rows top to bottom, each left to right, means all three totals exist before they are read.
A query uses the same rule with bigger pieces. The bottom-right total holds the rectangle plus the strip above and the strip to its left. Subtracting both strips removes the block where they overlap twice, so adding prefix[r1][c1] back once leaves exactly the rectangle.
Going deeper
3 more ideas
Why add the corner back
The area above the rectangle and the area to its left overlap in the top-left corner block. Subtracting both removes that block twice, so it must be added back once. This add-and-subtract-the-overlap rule is called inclusion-exclusion, and the same rule builds the table in the first place.
Window around every cell
To get the total of the square of radius k around each cell, clamp the square to the grid (r1 = Math.max(0, r - k), r2 = Math.min(rows - 1, r + k), and the same for columns) and use the rectangle formula. That turns an O(k^2) job per cell into O(1).
Cost
Building takes O(rows * cols) time and space. Each rectangle question takes O(1). Searching all rectangles is still O(rows^2 * cols^2), but each check is instant instead of costing the rectangle's area.
Work it by hand
Every step in a table, with why
Build the table for a grid with 2 rows and 3 columns, then add up two rectangles.
grid = [[2, 5, 1], [4, 0, 3]]
| Step | Cell or query | Value | Above + left - corner | Stored or returned | Why |
|---|---|---|---|---|---|
| 1 | (0, 0) | 2 | 0 + 0 - 0 | prefix[1][1] = 2 | Cells in the top row and left column read the zero row and zero column, so no bounds checks are needed. |
| 2 | (0, 1) | 5 | 0 + 2 - 0 | prefix[1][2] = 7 | The total to the left is 2, so the top-left rectangle ending here holds 2 + 5. |
| 3 | (0, 2) | 1 | 0 + 7 - 0 | prefix[1][3] = 8 | The whole first row adds up to 8. |
| 4 | (1, 0) | 4 | 2 + 0 - 0 | prefix[2][1] = 6 | The total above is 2. The left column so far holds 2 + 4. |
| 5 | (1, 1) | 0 | 7 + 6 - 2 | prefix[2][2] = 11 | Above (7) and left (6) both contain the cell (0, 0), worth 2, so it is subtracted once. 2 + 5 + 4 + 0 = 11. |
| 6 | (1, 2) | 3 | 8 + 11 - 7 | prefix[2][3] = 15 | The overlap is the 7 in prefix[1][2]. The last slot is the whole grid: 15. |
| 7 | regionSum(prefix, 0, 1, 1, 2) | - | 15 - 0 - 6 + 0 | returns 9 | The right two columns: the whole total, minus nothing above, minus the left column (6). That is 5 + 1 + 0 + 3 = 9. |
| 8 | regionSum(prefix, 1, 1, 1, 2) | - | 15 - 8 - 6 + 2 | returns 3 | The bottom-right two cells, 0 and 3: subtract the row above (8) and the column to the left (6), then add back the corner (2) that was subtracted twice. |
The table is [[0, 0, 0, 0], [0, 2, 7, 8], [0, 6, 11, 15]], filled in 6 steps. Each rectangle then took four reads: 9 for the right two columns and 3 for the bottom-right two cells.
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| 2D prefix sums | O(rows × cols) | O(rows × cols) | The grid doesn't change and you'll ask many rectangle questions. |
| Add each rectangle cell by cell | O(q × rows × cols) | O(1) | Very few questions, or tiny rectangles. |
| Prefix sums per row | O(q × rows) | O(rows × cols) | Rectangles are short, or you already have row totals and want simpler code. |
| 2D Fenwick tree | O(q × log n × log m) | O(rows × cols) | Cells change between questions, so each update and each query must be fast. |
Extra memory: O(rows × cols): the table has (rows + 1) × (cols + 1) numbers.
How the steps grow
- 2D prefix sums, Prefix sums per row
O(rows × cols) - Add each rectangle cell by cell
O(q × rows × cols) - 2D Fenwick tree
O(q × log n × log m)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| 2D prefix sums | 100 | 1 million | 1 trillion |
| Add each rectangle cell by cell | 1,000 | 1 billion | more than a quadrillion |
| Prefix sums per row | 100 | 1 million | 1 trillion |
| 2D Fenwick tree | 110 | 99,317 | 397 million |
Inputs that need care
5 tricky inputs
- An empty grid:
grid = [] grid[0].lengththrows aTypeError, becausegrid[0]isundefined. Return[[0]]early whengrid.lengthis 0.- One row:
grid = [[3, 1, 4]] - It works as a 1D prefix sum with an extra zero row on top:
prefix[1]is[0, 3, 4, 8]. - A single-cell rectangle:
r1 = r2,c1 = c2 - The four terms leave just that cell's value. For cell
(1, 1)in the trace,11 - 7 - 6 + 2 = 0. - A rectangle touching the top or left edge
r1 = 0orc1 = 0reads the zero row or column, so the formula needs no special case.- Rows of different lengths
- The code assumes every row has
grid[0].lengthcells. A shorter row readsundefinedand fills the table withNaN. Pad rows or check lengths first.
Variations and follow-ups
Twists interviewers add
Counting cells instead of adding values
Store 1 where a cell meets a condition and 0 elsewhere. Then the same table counts, for example, how many blocked cells a rectangle has, so "is this square all open?" is one query.
Adding to rectangles: the 2D difference array
To add v to a whole rectangle many times, write +v and -v at its four corners in a difference grid, then build a 2D prefix sum of it once at the end.
Largest-sum rectangle
Fix a top row and a bottom row, add each column between them into one array, and run Kadane's algorithm on it. Over all row pairs this costs O(rows² × cols).
Three dimensions
The rule extends to cubes: a box sum uses eight corners, with signs that alternate the same way. Adding and subtracting overlaps like this is called inclusion-exclusion.
In an interview
Spot it, explain it, answer follow-ups
- Spot it from "sum of a sub-rectangle", "many queries on a matrix", "sum of the block around each cell", or "count the 1s in a square".
- Draw the four regions as you explain: the big top-left rectangle, the strip above, the strip to the left, and the corner that was subtracted twice.
- Test by hand: a rectangle at the top-left corner, a single cell, and the whole grid. These catch the shift between grid indexes and table indexes.
- The usual follow-up is "what if cells change?". Answer: a 2D Fenwick tree, with
O(log rows × log cols)per update and per query.
Where frontend code uses it
The same idea in real UI code
- Image filters such as a box blur can use a summed-area table (a 2D prefix sum) so each pixel's average costs the same whatever the blur radius.
- Heatmap dashboards answer "total activity in this selected region" instantly while the user drags a selection box.
- Spreadsheet-style grids can show the sum of a selected range of cells without re-adding every cell on each mouse move.