Abstract / Summary

Given a matrix and multiple submatrix ranges, increase each value in every specified submatrix by one.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 74% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Matrix
• Prefix Sum

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes the result of a series of rectangular addition queries on an n × n grid. Each query adds 1 to every cell inside the rectangle defined by its top-left corner (y1, x1) and bottom-right corner (y2, x2)*. The algorithm builds the final grid in two linear passes: first it records column-wise delta changes for each row, then it converts those deltas into absolute values using a prefix-sum operation. The design avoids nested loops over the entire rectangle for each query, which keeps the work proportional to the total height of all queried rectangles rather than their area.

Initialization

size = n
result = []
for i in range(size):
    result.append([0] * (size + 1))

A two-dimensional list named result is created with n rows. Each row contains n + 1 elements, the extra column serving as a sentinel that simplifies later subtraction without needing explicit bounds checks. All entries start at 0, establishing a clean slate for delta accumulation.

First Pass - Setting Deltas

for y1, x1, y2, x2 in queries:
    for y in range(y1, y2 + 1):
        result[y][x1]     += 1
        result[y][x2 + 1] -= 1

For every query the outer loop iterates over the rows that belong to the rectangle. Within each affected row the algorithm increments the cell at the left edge x1 and decrements the cell just beyond the right edge x2 + 1. This pattern creates a difference array per row: after processing all queries, the cumulative sum of a row will reflect the total number of additions that should appear in each column. The extra column guarantees that the decrement operation never writes past the allocated memory, even when x2 is the last column of the grid.

Edge conditions handled in this stage include:

• Queries that span the entire width of the grid, where x2 equals n - 1. The sentinel column at index n absorbs the subtraction safely.
• Queries that consist of a single row (when y1 equals y2) or a single column (when x1 equals x2). The loop still executes correctly because the range includes both endpoints.
• An empty queries list. The loop body is never entered, leaving the delta matrix untouched and ready for the next pass.

Second Pass - Converting Deltas to Absolute Values

for y in range(size):
    result[y] = list(accumulate(result[y]))
    result[y].pop()

Each row is transformed by applying itertools.accumulate, which computes the running total of the delta values. The resulting list now holds the exact count of additions for every column in that row. The final pop() removes the sentinel element that was only needed for the subtraction step, restoring the row to the original n length.

The use of accumulate offers a concise, C-implemented routine that iterates once over each row, delivering a speed advantage over a manual Python loop. By overwriting the original row with the accumulated list, the code reuses the allocated memory, reducing pressure on the garbage collector.

Edge Cases Addressed in the Prefix Pass

• Rows that never received any delta updates remain a sequence of zeros; accumulate produces a zero-filled row, and the subsequent pop() removes the extra column, yielding the correct all-zero result for that row.
• When a query touches the rightmost column, the decrement placed at index n does not appear in the final output because the sentinel is removed after accumulation, ensuring the rightmost column reflects the intended increment count.
• The algorithm gracefully handles the situation where n is 0. The initialization creates an empty result list, both passes iterate over empty ranges, and the function returns an empty list, matching the expected empty grid.

Performance Optimizations

The implementation incorporates several deliberate choices that improve runtime efficiency:

• Pre-allocating the grid with a fixed width of n + 1 avoids repeated list resizing during delta updates.
• Storing only column deltas per row eliminates the need for a full two-dimensional difference matrix, cutting memory usage roughly in half compared with a naïve n × n* difference array.
• Leveraging itertools.accumulate provides a fast, low-overhead prefix-sum computation that runs in compiled code rather than pure Python.
• Updating rows in place and discarding the sentinel column with a single pop() keeps the overall memory footprint tight and avoids creating additional temporary structures.

Through these techniques the algorithm processes m queries in O(total height of rectangles + n²) time while maintaining a compact O(n²) space layout, delivering a practical solution for large grids with many overlapping range additions.

Imagine a large grid of empty square boxes laid out on the floor. The goal is to fill some of these boxes with blocks to make a picture. The number n tells the size of the room, so if n is three, there are three rows and three columns of boxes.

The code starts by creating this grid and filling every single box with a zero. This is like laying out blank paper before starting to draw.

Next, a list of instructions arrives. Each instruction says to take a specific rectangular area on the grid and add one block to every box inside that shape. Instead of placing blocks one by one, the code marks the edges of the shape with special notes. It puts a plus one at the start of a row and a minus one at the end of the area. These notes act like signals that say start counting now and stop counting soon.

After the notes are placed, the code walks across each row of the grid. It keeps a running total of the notes it finds. As it moves along, it adds up the pluses and minuses to figure out exactly how many blocks should be in each box. It is similar to counting how many layers of stickers are on a page by looking at where the stickers begin and end. Once the math for a row is finished, the extra note at the very end is taken away so the grid looks clean and ready. Each row is updated until every box has the correct number of blocks showing.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java			Python		TS
	WalkCCC	C++
	leetcode.ca	C++		Java	C#	Go	Python	Rust	TS
	Progiez	C++		Java			Python
github	charles-wangkai			Java
	fsq	C++
	JoshCrozier		JS
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
wisdompeak	C++
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality