Max Sum of Rectangle No Larger Than K

Max Sum of Rectangle No Larger Than K stacks two classic tricks on top of each other: collapsing a 2-D problem into a 1-D one by fixing a pair of columns, and finding the largest subarray sum that stays under a cap with a running prefix and an ordered set.

The slow way first

The brute force enumerates every rectangle by its four edges — top row, bottom row, left column, right column — and sums it. That is four nested loops to pick the box plus more work to add it up: roughly O(m² n² · mn). Hopeless for anything but tiny grids.

The first cut: do not re-pick all four edges independently. If we fix the left and right columns, every rectangle between them is just a contiguous band of rows. So we can collapse those columns into a single 1-D array of row sums and ask a much smaller question about that array.

The idea: collapse to 1-D, then cap the subarray sum

For a fixed column pair we now have a 1-D array row_sums. We want its largest subarray sum that is <= k. Keep a running prefix and an ordered set of every earlier prefix. A subarray ending here has sum prefix - earlier_prefix; to make that <= k and as large as possible, we want the smallest earlier prefix that is >= prefix - k. An ordered set finds it with a binary search in O(log m).

Walk through it

Step through the animation. The L and R markers pick a column pair; the row-sum array updates as R slides right (we just add the new column, never recompute). For each pair we run the 1-D scan and update best. With k = 2, columns 0..2 give row sums [2, 1], whose best capped subarray is 2 — exactly k, so we cannot do better.

Pseudocode

best = -infinity
for left in all columns:
    row_sums = [0 for each row]
    for right from left to last column:
        add column "right" into every row_sums[r]
        # now find the largest subarray sum of row_sums that is <= k
        seen = ordered set containing {0}
        prefix = 0
        for s in row_sums:
            prefix += s
            target = prefix - k
            earlier = smallest value in seen that is >= target
            if earlier exists:
                best = max(best, prefix - earlier)
            add prefix to seen
return best

The Python solution

def max_sum_rect(matrix, k):
    cols = len(matrix[0])
    best = float("-inf")
    for left in range(cols):
        row_sums = [0] * len(matrix)
        for right in range(left, cols):
            for r in range(len(matrix)):
                row_sums[r] += matrix[r][right]
            seen = SortedList([0])
            prefix = 0
            for s in row_sums:
                prefix += s
                j = seen.bisect_left(prefix - k)
                if j < len(seen):
                    best = max(best, prefix - seen[j])
                seen.add(prefix)
    return best

• left pins the left edge; row_sums starts fresh for each new left.
• As right slides outward we only add column right into each row sum, so building the band is cheap.
• seen is an ordered set (from sortedcontainers) seeded with 0 — the empty prefix, which represents a subarray that starts at the very beginning.
• prefix - k is the target: we want the smallest earlier prefix that is >= target, so the gap prefix - earlier lands <= k.
• bisect_left finds the insertion point for prefix - k; seen[j] is that smallest qualifying earlier prefix, and prefix - seen[j] is the best capped subarray ending here.

Complexity

Pick the smaller dimension as the inner one: loop columns over the wider side so the ordered-set scan runs over the shorter side. The space is O(m) for the row sums and the ordered set.

When this pattern shows up

Practice