Max Sum of Rectangle No Larger Than K: 2D to 1D with Binary Search

LeetCode 363: Max Sum of Rectangle No Larger Than K gives you a 2D matrix of integers and an integer k. Your task: find the rectangle (contiguous submatrix) whose element sum is as large as possible without exceeding k, and return that sum.

If the constraint were just "find the maximum rectangle sum" with no upper bound, you could reduce the problem to maximum subarray and use Kadane's algorithm. But the "no larger than k" constraint changes everything. Kadane's always picks up positive contributions greedily, so you cannot plug k in and call it done. You need a different tool for the bounded version, and that tool is a sorted set with binary search on prefix sums.

Reducing 2D to 1D: fix left and right column boundaries

The first move is to reduce the 2D problem to a 1D problem you can actually solve efficiently.

Fix a left column L and a right column R. For each row i, compute rowSum[i] as the sum of matrix[i][L] through matrix[i][R] inclusive. You now have a 1D array where rowSum[i] represents the total contribution of row i to any rectangle that spans columns L through R.

Any rectangle within those column boundaries is determined entirely by which rows it includes. So the 2D question "what is the maximum rectangle sum no larger than k between columns L and R?" becomes the 1D question "what is the maximum subarray sum no larger than k in rowSums?"

You iterate over all pairs (L, R) with 0 <= L <= R < n. For each pair, you build rowSums in O(m) time by extending the previous rowSums array as R moves right. Then you solve the 1D subproblem on that array. The outer loop over column pairs is O(n^2), and the 1D subproblem is solved once per pair.

Solving the 1D subproblem: prefix sums + sorted set

Given a 1D array rowSums and a target k, you want the maximum subarray sum that is no larger than k.

Define prefix sums P where P[0] = 0 and P[i] = P[i-1] + rowSums[i-1]. A subarray from row a to row b (inclusive) has sum P[b+1] - P[a]. You want the maximum value of P[b+1] - P[a] subject to the constraint that P[b+1] - P[a] <= k, which rearranges to P[a] >= P[b+1] - k.

So as you scan b from 0 to m-1, you want the smallest P[a] in the set of previously seen prefix sums that is at least P[b+1] - k. If such a value exists, the difference P[b+1] - P[a] is valid and you update your best result.

Maintaining the prefix sums in a sorted list and using bisect_left to find the target in O(log m) gives you the 1D subproblem in O(m log m) total.

The code

from sortedcontainers import SortedList

def maxSumSubmatrix(matrix, k):
    m, n = len(matrix), len(matrix[0])
    ans = float('-inf')
    for l in range(n):
        row_sums = [0] * m
        for r in range(l, n):
            for i in range(m):
                row_sums[i] += matrix[i][r]
            sl = SortedList([0])
            curr = 0
            for s in row_sums:
                curr += s
                idx = sl.bisect_left(curr - k)
                if idx < len(sl):
                    ans = max(ans, curr - sl[idx])
                sl.add(curr)
    return ans

A few things to notice:

1. row_sums[i] += matrix[i][r] extends the row sums as r moves right, so you never recompute from scratch for each column pair. Each inner r loop costs O(m) for the update.
2. The SortedList starts with [0] to represent the empty prefix P[0] = 0. This handles subarrays that start at row 0.
3. sl.bisect_left(curr - k) finds the index of the smallest value in the set that is at least curr - k. If that index is valid, curr - sl[idx] is the best subarray sum ending at the current row for this column pair.
4. You add curr to the set after querying, so each prefix sum is available for future rows.

Step-by-step walkthrough

The walkthrough traces rowSums = [2, 1] with k = 2. At step 2, the sorted set contains only {0}, and curr - k = 0, so the binary search finds 0 immediately. The difference 2 - 0 = 2 is valid and becomes the best. At step 3, curr = 3 and curr - k = 1. The smallest value in {0, 2} that is at least 1 is 2, giving diff = 1, which does not beat the current best of 2. Final answer: 2.

Complexity

Wait, that is not quite right. For each of the O(n^2) column pairs, you spend O(m) building rowSums (amortized, since you extend rather than rebuild) and O(m log m) on the sorted set pass. So the total is O(n^2 * m log m), which is the same as O(m * n^2 * log m) when you think of column pairs first.

If m is larger than n, you can transpose the matrix first and treat rows as columns, keeping the sorted set size at min(m, n). The binary search cost becomes O(log min(m, n)).

Note on notation: m is the number of rows and n is the number of columns throughout. If the matrix is tall (many rows), swapping the iteration axes so you fix row boundaries instead gives the same algorithm with better constants.

Building blocks: two patterns combined

This problem layers two reusable techniques.

Fix two boundaries and compress. You have seen this in Maximal Rectangle: fix a left boundary and a right boundary (or a top and a bottom), then collapse the enclosed region into a 1D array. That 1D array summarizes every rectangle within those boundaries, and you solve a 1D problem on it. The technique converts a hard 2D problem into a sequence of tractable 1D problems.

Sorted set plus binary search for a constrained prefix sum. Whenever you need "the maximum subarray sum no larger than k," the pattern is: maintain a sorted container of prefix sums seen so far; for each new prefix sum curr, binary search for the smallest existing prefix sum that is at least curr - k; if found, update your answer. This same pattern applies any time you need a "best match within a bound" over a stream of values.

Missing either insight gives you a solution that is conceptually correct but too slow for the given constraints. The column-pair reduction without the sorted set leaves you with a O(m^2) inner loop. The sorted set without the reduction leaves you staring at a 2D problem you cannot directly apply it to.

Edge cases

• k is larger than the total matrix sum. Any rectangle qualifies, so the answer is simply the maximum rectangle sum. The algorithm handles this without special cases: bisect_left will always find a match since the total sum is no larger than k.
• k is very negative. Only rectangles with highly negative sums qualify. This is rare in practice but valid. The algorithm still works correctly because the sorted set and binary search do not assume anything about the sign of the values.
• Single row or single column. With one row, the column-pair loop covers all subarrays directly. With one column, each column pair degenerates to a single column, and rowSums is just the column values. Both cases fall out of the general code without modification.
• All negative values. No rectangle sums will be positive, but the algorithm correctly finds the least-negative sum no larger than k by comparing all valid prefix sum differences.

From understanding to recall

There are two separate insights to internalize: the 2D-to-1D reduction, and the sorted-set trick for constrained subarray sums. Missing either one gives you a solution that is conceptually coherent but too slow for the hard constraint on matrix size.

The reduction is the easier piece to remember. "Fix two column boundaries, compress each row into a single number, solve a 1D problem" is a short sentence. The sorted-set trick is trickier because it requires keeping two things in sync: the invariant that sl holds all prefix sums seen before the current index, and the algebraic rearrangement that turns "subarray sum no larger than k" into "find smallest prefix sum at least curr - k."

Spaced repetition is the right tool here because the two insights need to stay linked in memory, not just individually recalled. You want to be able to write the full solution from scratch, which means both pieces need to be active at the same time. Drilling one without the other produces a half-solution that stalls in an interview.

Related posts

• Maximal Rectangle - the same "fix column boundaries" technique applied to a different objective
• Range Sum Query 2D Immutable - 2D prefix sums, which underlie this problem's row compression step
• Maximum Subarray - the unconstrained 1D max subarray problem; this problem adds the "no larger than k" constraint