LeetCode 363: Max Sum of Rectangle No Larger Than K

Problem Restatement

We are given an m x n integer matrix and an integer k.

We need to find the maximum sum of any rectangle in the matrix such that the sum is no larger than k.

A rectangle means a contiguous block of rows and columns.

The problem guarantees that at least one rectangle has sum less than or equal to k. The official example uses matrix = [[1,0,1],[0,-2,3]] and k = 2, whose answer is 2.

Input and Output

Example function shape:

def maxSumSubmatrix(matrix: list[list[int]], k: int) -> int:
    ...

Examples

Example 1:

matrix = [
    [1, 0, 1],
    [0, -2, 3],
]
k = 2

One valid rectangle is:

[
    [0, 1],
    [-2, 3],
]

Its sum is:

0 + 1 - 2 + 3 = 2

Since 2 <= k, and no larger valid rectangle sum exists, the answer is:

2

Example 2:

matrix = [[2, 2, -1]]
k = 3

The best rectangle is:

[2, -1]

Its sum is:

1

But a better valid rectangle is:

[2, 2, -1]

Its sum is:

3

So the answer is:

3

First Thought: Try Every Rectangle

A brute force solution is to enumerate every rectangle.

A rectangle is defined by:

top row
bottom row
left column
right column

There are O(m^2 * n^2) possible rectangles.

If we use a 2D prefix sum, each rectangle sum can be computed in O(1).

So brute force costs:

O(m^2 * n^2)

With m, n <= 100, this can be too slow.

We need to reduce the problem.

Key Insight

Fix two row boundaries:

top
bottom

Then every rectangle between these two rows becomes a subarray problem over columns.

For each column, compute the sum between top and bottom.

Example:

matrix = [
    [1, 0, 1],
    [0, -2, 3],
]

If top = 0 and bottom = 1, the column sums are:

So the 2D problem becomes:

nums = [1, -2, 4]

Now we need the maximum subarray sum no larger than k.

That is a 1D problem.

The 1D Problem

Given an array nums, find the maximum subarray sum no larger than k.

Use prefix sums.

For a subarray ending at the current position:

subarray_sum = current_prefix - previous_prefix

We need:

current_prefix - previous_prefix <= k

Rearrange:

previous_prefix >= current_prefix - k

So for each current_prefix, we want the smallest previous prefix that is at least:

current_prefix - k

Then the subarray sum will be as large as possible while staying <= k.

This needs an ordered set of prefix sums with binary search.

Python does not have a built-in balanced tree, so for LeetCode Python we can use a sorted list with bisect.insort.

Since matrix dimensions are only up to 100, this is acceptable.

Algorithm

To reduce work, compress along the smaller dimension.

If rows are more than columns, keep the normal row-pair approach.

If columns are more than rows, we can still use row pairs. For simplicity, this guide implements row pairs directly.

Steps:

1. Let m be row count and n be column count.
2. Initialize best = -inf.
3. For each top row:
   • Create col_sums = [0] * n.
4. For each bottom row from top to m - 1:
   • Add the current bottom row into col_sums.
   • Solve the 1D max subarray no larger than k on col_sums.
   • Update best.
5. Return best.

The 1D helper:

1. Start with sorted prefix list [0].
2. Set prefix = 0.
3. For each number:
   • Add it to prefix.
   • Find the first stored prefix >= prefix - k.
   • Use it to update the best answer.
   • Insert prefix into the sorted prefix list.

Correctness

Fix any pair of rows top and bottom.

For this fixed row range, each rectangle is determined only by its left and right columns. The column-compressed array stores the sum of each column between those two rows. Therefore, the sum of any rectangle with those row boundaries equals the sum of a contiguous subarray in the compressed array.

The 1D helper considers every possible subarray through prefix sums. For each ending position, it finds the smallest previous prefix that is at least current_prefix - k. This gives the largest subarray sum ending at that position while staying no larger than k.

Because the outer loops try every possible pair of row boundaries, and the helper finds the best valid column range for each pair, every rectangle in the matrix is considered.

The algorithm keeps the maximum valid sum over all row pairs, so the returned value is the maximum rectangle sum no larger than k.

Complexity

Let m be the number of rows and n be the number of columns.

The ideal complexity is:

O(m^2 * n log n)

Using Python list insertion, insertion costs O(n), so the practical Python implementation is:

O(m^2 * n^2)

For 100 x 100, this still commonly passes.

With a real ordered set, the optimized complexity is:

O(min(m, n)^2 * max(m, n) * log(max(m, n)))

Implementation

from bisect import bisect_left, insort
from math import inf

class Solution:
    def maxSumSubmatrix(self, matrix: list[list[int]], k: int) -> int:
        m = len(matrix)
        n = len(matrix[0])

        best = -inf

        for top in range(m):
            col_sums = [0] * n

            for bottom in range(top, m):
                for col in range(n):
                    col_sums[col] += matrix[bottom][col]

                best = max(best, self._max_subarray_no_larger_than_k(col_sums, k))

                if best == k:
                    return k

        return best

    def _max_subarray_no_larger_than_k(self, nums: list[int], k: int) -> int:
        prefixes = [0]
        prefix = 0
        best = -inf

        for num in nums:
            prefix += num

            target = prefix - k
            index = bisect_left(prefixes, target)

            if index < len(prefixes):
                best = max(best, prefix - prefixes[index])

            insort(prefixes, prefix)

        return best

Code Explanation

The outer loop chooses the top row:

for top in range(m):

For each top row, we reset column sums:

col_sums = [0] * n

Then we move the bottom row downward:

for bottom in range(top, m):

Each time, we add the new row into col_sums:

for col in range(n):
    col_sums[col] += matrix[bottom][col]

Now col_sums[col] is the sum from row top to row bottom in that column.

Then we solve the 1D problem:

best = max(best, self._max_subarray_no_larger_than_k(col_sums, k))

If we ever reach exactly k, we can return immediately:

if best == k:
    return k

No answer can be larger than k.

Inside the helper, we store prefix sums in sorted order:

prefixes = [0]

The initial 0 allows subarrays starting at index 0.

For each prefix, we need the smallest previous prefix at least prefix - k:

target = prefix - k
index = bisect_left(prefixes, target)

If such a prefix exists, it forms a valid candidate:

best = max(best, prefix - prefixes[index])

Then insert the current prefix for later subarrays:

insort(prefixes, prefix)

Testing

def run_tests():
    s = Solution()

    assert s.maxSumSubmatrix(
        [[1, 0, 1], [0, -2, 3]],
        2,
    ) == 2

    assert s.maxSumSubmatrix(
        [[2, 2, -1]],
        3,
    ) == 3

    assert s.maxSumSubmatrix(
        [[5]],
        4,
    ) == -float("inf")  # invalid under LeetCode guarantee, no rectangle <= k

    assert s.maxSumSubmatrix(
        [[5]],
        5,
    ) == 5

    assert s.maxSumSubmatrix(
        [[-1, -2], [-3, -4]],
        -2,
    ) == -2

    assert s.maxSumSubmatrix(
        [[2, 2, -1], [3, -2, 4]],
        6,
    ) == 6

    print("all tests passed")

run_tests()

Test meaning:

Note: the [[5]], k = 4 test violates the LeetCode guarantee that a valid rectangle exists. In a production version, remove that test or return a sentinel only if invalid input is allowed.