Max Sum of Rectangle No Larger Than K

Intuition

Any rectangle is bounded by a left and a right column, so we iterate over every pair (left, right). For a fixed pair we compress each row into a single number: the sum of that row's entries between left and right. That turns the task into finding the maximum subarray sum not exceeding k over a 1D array. Using running prefix sums, a subarray sum equals currentPrefix minus some earlier prefix; to keep it at most k we need the smallest earlier prefix that is at least currentPrefix minus k. Storing seen prefixes in an ordered structure lets us binary search for that value quickly, and languages without a built-in ordered set can maintain a sorted list with binary insertion instead.

Algorithm walkthrough

1. 1Loop over every left column; reset a rowSums array of length equal to the number of rows to all zeros.
2. 2For each right column from left onward, add matrix[r][right] into rowSums[r] so rowSums holds the compressed strip between left and right.
3. 3Scan rowSums building a running prefix; start an ordered set of prefixes containing 0.
4. 4At each step, search the ordered set for the smallest prefix that is at least currentPrefix minus k; if found, currentPrefix minus that prefix is a candidate answer, and we keep the best candidate that does not exceed k.
5. 5Insert the current prefix into the ordered set and continue.
6. 6After all column pairs are processed, return the best answer found.

Implementation

import bisect
from typing import List

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        rows, cols = len(matrix), len(matrix[0])
        best = float('-inf')
        for left in range(cols):
            row_sums = [0] * rows
            for right in range(left, cols):
                for r in range(rows):
                    row_sums[r] += matrix[r][right]
                # Best subarray sum <= k via sorted prefixes
                prefixes = [0]
                prefix = 0
                for s in row_sums:
                    prefix += s
                    idx = bisect.bisect_left(prefixes, prefix - k)
                    if idx < len(prefixes):
                        best = max(best, prefix - prefixes[idx])
                    bisect.insort(prefixes, prefix)
        return best