Max Sum of Rectangle No Larger Than K: Row Compression Plus Sorted-Set Search

Problem Statement#

Given an m x n integer matrix and an integer k, find the maximum sum of a non-empty rectangle inside the matrix such that the sum is at most k. The rectangle must consist of contiguous rows and contiguous columns. Constraints typically allow m, n up to about 100, with values up to 1e5 in magnitude. There is always at least one rectangle whose sum does not exceed k.

Why This Problem Matters#

This is one of the cleanest interview problems that stitches together five distinct ideas: 2D to 1D reduction, Kadane's algorithm, prefix sums, ordered set lookup, and the at-most-k twist that breaks naive Kadane. Companies like Google, Amazon, Bloomberg, and Goldman Sachs use it to check whether you can compose techniques rather than memorize a single trick. It also opens the door to a Fenwick tree (BIT) or segment tree variant when the matrix is huge and column counts dominate.

If you can articulate why "max subarray sum at most k" cannot be solved by Kadane alone but can be solved by a sorted set of prefix sums, you have shown the kind of layered reasoning that senior-level interviewers look for.

The Core Insight#

The 2D problem reduces to a 1D problem by fixing two row boundaries r1 and r2. For each column c, compute the column-wise sum across rows r1..r2 and store it in a 1D array colSum. Now any rectangle whose row span is [r1, r2] corresponds to some contiguous subarray of colSum. The 2D question "max rectangle sum bounded above by k" becomes the 1D question "max subarray sum of colSum bounded above by k."

Kadane gives you the unconstrained max subarray sum, but it does not respect the at-most-k cap. Instead, walk left to right computing prefix sums of colSum. For each running prefix cur, the subarray ending here that does not exceed k is cur - p for any earlier prefix p with p greater than or equal to cur - k. So among all earlier prefixes, you want the smallest one that is at least cur - k. A sorted set with bisect_left finds it in O(log n).

The classic complexity is therefore O(m^2 * n log n). If n is much smaller than m, swap the loops so the inner dimension is the smaller one. That single swap can be the difference between accepted and TLE.

For very wide matrices and many queries, a Fenwick tree (BIT) or order-statistic segment tree over compressed prefix sums achieves the same lookup, and supports range queries on top.

Visual Dry Run#

Take a 3x3 matrix, k = 8.

matrix:
 1  0  1
 0 -2  3
 0  3  0
 
Iterate row pairs:
 r1=0,r2=0 -> colSum = [1, 0, 1]
 r1=0,r2=1 -> colSum = [1,-2, 4]
 r1=0,r2=2 -> colSum = [1, 1, 4]
 r1=1,r2=1 -> colSum = [0,-2, 3]
 r1=1,r2=2 -> colSum = [0, 1, 3]
 r1=2,r2=2 -> colSum = [0, 3, 0]
 
Inner pass for r1=1,r2=2, colSum=[0,1,3], k=8:
 prefixSet = {0}
 cur=0:  target=cur-k=-8, smallest prefix >= -8 is 0, candidate = 0-0 = 0, best=0
        insert 0 -> {0}
 cur=1:  target=-7, smallest prefix >= -7 is 0, candidate = 1, best=1
        insert 1 -> {0,1}
 cur=4:  target=-4, smallest prefix >= -4 is 0, candidate = 4, best=4

Global best across all row pairs is 6, which is at most k = 8, so the answer is 6.

The inner sorted set is the workhorse: it transforms the at-most-k constraint into a single ordered lookup per right endpoint.

Solution (Optimal)#

import bisect
from typing import List
 
class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        m, n = len(matrix), len(matrix[0])
        # Iterate the smaller dimension on the outside for speed
        if m > n:
            return self.maxSumSubmatrix([list(col) for col in zip(*matrix)], k)
        best = float('-inf')
        for r1 in range(m):
            colSum = [0] * n
            for r2 in range(r1, m):
                for c in range(n):
                    colSum[c] += matrix[r2][c]
                # Find max subarray sum of colSum bounded above by k
                prefixes = [0]
                cur = 0
                for v in colSum:
                    cur += v
                    target = cur - k
                    idx = bisect.bisect_left(prefixes, target)
                    if idx < len(prefixes):
                        best = max(best, cur - prefixes[idx])
                    bisect.insort(prefixes, cur)
        return best

function maxSumSubmatrix(matrix, k) {
  let m = matrix.length;
  let n = matrix[0].length;
  // Use smaller dimension as outer loop
  if (m > n) {
    const t = Array.from({ length: n }, (_, i) =>
      Array.from({ length: m }, (_, j) => matrix[j][i])
    );
    return maxSumSubmatrix(t, k);
  }
  let best = -Infinity;
  for (let r1 = 0; r1 < m; r1++) {
    const colSum = new Array(n).fill(0);
    for (let r2 = r1; r2 < m; r2++) {
      for (let c = 0; c < n; c++) colSum[c] += matrix[r2][c];
      // Sorted list of prefixes; binary search for cur - k
      const prefixes = [0];
      let cur = 0;
      for (const v of colSum) {
        cur += v;
        const target = cur - k;
        // bisect_left
        let lo = 0;
        let hi = prefixes.length;
        while (lo < hi) {
          const mid = (lo + hi) >> 1;
          if (prefixes[mid] < target) lo = mid + 1;
          else hi = mid;
        }
        if (lo < prefixes.length) {
          best = Math.max(best, cur - prefixes[lo]);
        }
        // insort (linear in JS without a balanced BST)
        let ins = 0;
        let ihi = prefixes.length;
        while (ins < ihi) {
          const mid = (ins + ihi) >> 1;
          if (prefixes[mid] < cur) ins = mid + 1;
          else ihi = mid;
        }
        prefixes.splice(ins, 0, cur);
      }
    }
  }
  return best;
}

Complexity. With Python's bisect.insort, each insertion is O(n), so the inner loop is O(n^2) per row pair, giving O(m^2 * n^2) in the worst case. Replacing the sorted list with a balanced BST or an order-statistic Fenwick tree (BIT) brings the inner loop to O(n log n) and the total to O(m^2 * n log n). The standard interview-acceptable answer is the latter; the JavaScript snippet above uses a sorted array for clarity.

If m is much larger than n, transpose the matrix so the outer two loops iterate over the smaller dimension. This single optimisation is often the difference between AC and TLE.

Common Mistakes#

• Trying to apply Kadane directly to find the max subarray sum at most k. Kadane finds the unconstrained max; the cap breaks the optimal-substructure property.
• Forgetting to seed the sorted set with 0. Without it, you cannot capture subarrays that start from index 0.
• Using bisect_right instead of bisect_left. You want the smallest prefix that is at least cur - k, which is bisect_left.
• Iterating the larger dimension on the outside. Always transpose so the outer two loops are over the smaller dimension.
• Resetting colSum to zero on every r2 iteration. The whole point is to extend colSum incrementally as you grow r2.
• Computing cur - prefixes[idx] without checking idx < len(prefixes). If no prefix qualifies, this row pair contributes nothing.

Interview Tips#

• Verbalise the reduction explicitly: "I will fix the two row boundaries, compress to a 1D array, and solve the 1D variant." That sentence alone earns half the credit.
• State why Kadane fails before showing the prefix-set fix. It demonstrates that you understand the constraint, not just the algorithm.
• Mention the dimension-swap optimisation. Senior interviewers love when you preempt obvious slowdowns.
• If asked about even larger inputs, mention a Fenwick tree (BIT) over compressed prefix sums or a segment tree variant for ordered queries. Both achieve the same O(log n) lookup with structured semantics.
• For follow-up questions, be ready to drop the at-most-k constraint and switch to plain Kadane in O(m^2 * n), the classic Maximum Sum Rectangle problem.

Follow-up Questions#

• LeetCode 53 Maximum Subarray and the 2D version Maximum Sum Rectangle. Same row-pair compression with Kadane on the inside, no sorted-set needed.
• Count submatrices summing to exactly target (LeetCode 1074). Same compression with a hashmap of prefix sums.
• Find the rectangle with sum closest to k. Same prefix-set scan, but track the closest candidate to k rather than the maximum at most k.
• Streaming version: rows arrive online. Maintain the column-sum arrays incrementally and re-run the inner pass per new row.
• Range update plus range query variant. Use a 2D Fenwick tree or 2D segment tree with lazy propagation, then run the same row compression on the augmented structure.

Key Takeaways#

• Fix two row boundaries to convert the 2D problem into a 1D max subarray sum at most k problem.
• The at-most-k constraint kills Kadane; a sorted set of prefix sums plus binary search is the right tool.
• Always iterate the smaller dimension on the outside to keep the m^2 factor small.
• Seed the sorted prefix structure with 0 and use bisect_left to find the smallest prefix that is at least cur - k.
• For huge matrices, a Fenwick tree (BIT) or segment tree over compressed prefix sums achieves O(log n) per inner step.
• The same row-compression template solves Maximum Sum Rectangle, count submatrices summing to target, and rectangle sum closest to k.