Max Sum Rectangle No Larger than K — BIT + Prefix

Problem

Find the max sum rectangle in the matrix with sum <= k.

Approach — Fix Row Boundaries + 1D Problem

For each pair of row boundaries (r1, r2):

Compress to 1D array (column sums)
Find max subarray sum <= k using prefix sums + sorted set (bisect for prefix - (prefix - k) >= 0)

Time: O(m² * n log n) | Space: O(n)

Solutions

Python

import bisect
class Solution:
    def maxSumSubmatrix(self, matrix: list[list[int]], k: int) -> int:
        m,n=len(matrix),len(matrix[0]); ans=float('-inf')
        for r1 in range(m):
            col_sum=[0]*n
            for r2 in range(r1,m):
                for c in range(n): col_sum[c]+=matrix[r2][c]
                # max subarray sum <= k
                prefix=[0]; cur=0
                for v in col_sum:
                    cur+=v
                    target=cur-k
                    idx=bisect.bisect_left(prefix,target)
                    if idx<len(prefix): ans=max(ans,cur-prefix[idx])
                    bisect.insort(prefix,cur)
        return ans

Complexity

Time: O(m² * n log n) | Space: O(n)