# 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

| Item | Meaning |
|---|---|
| Input | Integer matrix `matrix` and integer `k` |
| Output | Maximum rectangle sum `<= k` |
| Rectangle | Contiguous rows and contiguous columns |
| Values | Can be positive, zero, or negative |
| Constraints | `1 <= m, n <= 100` |

Example function shape:

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

## Examples

Example 1:

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

One valid rectangle is:

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

Its sum is:

```python
0 + 1 - 2 + 3 = 2
```

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

```python
2
```

Example 2:

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

The best rectangle is:

```python
[2, -1]
```

Its sum is:

```python
1
```

But a better valid rectangle is:

```python
[2, 2, -1]
```

Its sum is:

```python
3
```

So the answer is:

```python
3
```

## First Thought: Try Every Rectangle

A brute force solution is to enumerate every rectangle.

A rectangle is defined by:

```text
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:

```python
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:

```text
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:

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

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

| Column | Sum |
|---:|---:|
| `0` | `1 + 0 = 1` |
| `1` | `0 + (-2) = -2` |
| `2` | `1 + 3 = 4` |

So the 2D problem becomes:

```python
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:

```python
subarray_sum = current_prefix - previous_prefix
```

We need:

```python
current_prefix - previous_prefix <= k
```

Rearrange:

```python
previous_prefix >= current_prefix - k
```

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

```python
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.

| Operation | Time |
|---|---:|
| Row-pair enumeration | `O(m^2)` |
| Column compression per bottom row | `O(n)` |
| 1D ordered-prefix search | `O(n log n)` with a balanced tree |

The ideal complexity is:

```python
O(m^2 * n log n)
```

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

```python
O(m^2 * n^2)
```

For `100 x 100`, this still commonly passes.

With a real ordered set, the optimized complexity is:

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

## Implementation

```python
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:

```python
for top in range(m):
```

For each top row, we reset column sums:

```python
col_sums = [0] * n
```

Then we move the bottom row downward:

```python
for bottom in range(top, m):
```

Each time, we add the new row into `col_sums`:

```python
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:

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

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

```python
if best == k:
    return k
```

No answer can be larger than `k`.

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

```python
prefixes = [0]
```

The initial `0` allows subarrays starting at index `0`.

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

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

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

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

Then insert the current prefix for later subarrays:

```python
insort(prefixes, prefix)
```

## Testing

```python
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:

| Test | Why |
|---|---|
| Standard example | Checks mixed positive and negative values |
| Single row | Reduces to 1D case |
| Single cell equal to `k` | Exact match |
| All negative | Best answer can be negative |
| Exact `k` in larger matrix | Checks early return |

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.