Abstract / Summary

Find the largest sum of a rectangle in a matrix that does not exceed a given number.

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 46% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Matrix
• Ordered Set
• 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 implementation solves the problem of finding the maximum sum of any sub-matrix whose sum does not exceed a given limit k. It follows a classic two-dimensional prefix-sum strategy to enable constant-time rectangle sum queries, then enumerates all possible rectangles to locate the best candidate. The code is written in C++ and leverages the language’s ability to handle nested loops efficiently.

Prefix-sum construction

A helper matrix prefix is allocated with one extra row and column. This extra padding eliminates the need for boundary checks inside the inner loops. The construction iterates over every cell of the original matrix and accumulates the sum of the rectangle that spans from the origin to the current position.

std::vector<std::vector<int>> prefix(height + 1,
                                     std::vector<int>(width + 1, 0));

for (size_t y = 1; y <= height; y++)
    for (size_t x = 1; x <= width; x++)
    {
        prefix[y][x]  = matrix[y - 1][x - 1];
        prefix[y][x] += prefix[y][x - 1];
        prefix[y][x] += prefix[y - 1][x];
        prefix[y][x] -= prefix[y - 1][x - 1];
    }

Each entry prefix[y][x] stores the sum of the sub-matrix bounded by rows 0..y-1 and columns 0..x-1. The subtraction of prefix[y-1][x-1] corrects for the double-counted overlap.

Enumerating all rectangles

With the prefix matrix in place, the algorithm enumerates every possible rectangle by selecting its bottom-right corner (y, x) and its top-left corner (y2, x2). The sum of the rectangle is retrieved in constant time using the inclusion-exclusion principle.

for (size_t y = 1; y <= height; y++)
    for (size_t x = 1; x <= width; x++)
        for (int y2 = 0; y2 < int(y); y2++)
            for (int x2 = 0; x2 < int(x); x2++)
            {
                int rectangle = prefix[y][x];
                rectangle    -= prefix[y][x2];
                rectangle    -= prefix[y2][x];
                rectangle    += prefix[y2][x2];

The four-term expression extracts exactly the sum of the region bounded by rows y2..y-1 and columns x2..x-1.

Updating the result and early termination

Whenever a rectangle sum satisfies the constraint rectangle <= k and improves upon the current best, the result is updated. An immediate return occurs when the sum equals k, because no larger valid sum can exist.

                if (result < rectangle && rectangle <= k)
                {
                    result = rectangle;
                    if (result == k)
                        return result;
                }

This early-exit condition prevents unnecessary continuation once the optimal possible value is found.

Edge cases handled

The code gracefully handles matrices with a single row or a single column because the extra padding in prefix ensures that the inner loops still operate correctly. The initialization of result to the minimum integer value guarantees that even when all rectangle sums exceed k, the function will return a value that reflects the absence of a valid rectangle (the minimum sentinel). The loops use size_t for dimensions and cast to int only where necessary, preserving correctness for large matrix sizes while avoiding unsigned-underflow when iterating backward indices.

Performance considerations

The use of a two-dimensional prefix sum reduces each rectangle sum query to a constant-time arithmetic expression, eliminating the need for repeated scanning of matrix elements. The extra row and column in prefix remove conditional checks inside the innermost loop, allowing the compiler to generate tight loop bodies. The early-exit check if (result == k) return result; can dramatically cut the total number of iterations in cases where a perfect match is found early, especially for matrices containing large positive numbers. By relying on C++’s efficient loop execution and avoiding dynamic memory allocation inside the enumeration, the implementation achieves a performance profile that is acceptable for the problem constraints, even though the algorithmic complexity is higher than more advanced approaches.

Imagine you have a big sheet of graph paper covered in colorful square stickers, each with a number written on it. The goal of this game is to look at every possible rectangle you can draw on that paper, add up all the numbers inside each one, and find the largest total that stays smaller than or equal to a special target number.

First, the code builds a special map called a prefix. Think of this like a cheat sheet that helps add up the numbers in any rectangle super fast without having to count every single sticker one by one every time. It fills this map by looking at the stickers and keeping a running total of the numbers as it moves across and down the grid.

After the cheat sheet is ready, the computer starts looking at every rectangle it can possibly imagine. It uses four loops to pick every corner and side for these rectangles. For each one, it does a bit of quick math using the cheat sheet to instantly know the total value of all the numbers inside that shape.

While it does this, it keeps a record of the best total found so far that is still at or below that special target number. If it ever finds a rectangle that adds up to that exact target number, it shouts that it found the winner and stops looking, because it knows it cannot possibly do better than the target. It keeps doing this until it has checked every single possible rectangle on the sheet.

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++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java			Go			TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	charles-wangkai				Java
	chenyanzhe	C++
	everthis			JS
	fartem						Ruby
	fpdjsns	C++
	halfrost							Go
	JoshCrozier			JS
	linouk23	C++
	lkwq007		Python
	ruoru					Rust
	suxrobGM								C#
	trung-hn		Python
	vli02									C
	vthwang				Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
halfrost	Go
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
vli02	C
vthwang	Java
wisdompeak	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