Max Sum of Rectangle No Larger Than K
Problem
Given a matrix and integer k, find the maximum sum of any rectangular sub-matrix whose sum is ≤ k.
matrix = [[1,0,1],[0,-2,3]], k = 22from sortedcontainers import SortedList
def max_sum_submatrix(matrix, k):
rows, cols = len(matrix), len(matrix[0])
best = float("-inf")
for l in range(cols):
col_sums = [0] * rows
for r in range(l, cols):
for i in range(rows):
col_sums[i] += matrix[i][r]
seen = SortedList([0])
prefix = 0
for v in col_sums:
prefix += v
idx = seen.bisect_left(prefix - k)
if idx < len(seen):
best = max(best, prefix - seen[idx])
seen.add(prefix)
return bestfunction maxSumSubmatrix(matrix, k) {
const rows = matrix.length, cols = matrix[0].length;
let best = -Infinity;
for (let l = 0; l < cols; l++) {
const colSums = new Array(rows).fill(0);
for (let r = l; r < cols; r++) {
for (let i = 0; i < rows; i++) colSums[i] += matrix[i][r];
const seen = [0];
let prefix = 0;
for (const v of colSums) {
prefix += v;
// find smallest s in seen with prefix - s <= k, i.e. s >= prefix - k
let lo = 0, hi = seen.length;
while (lo < hi) { const m = (lo + hi) >> 1; if (seen[m] < prefix - k) lo = m + 1; else hi = m; }
if (lo < seen.length) best = Math.max(best, prefix - seen[lo]);
// insert prefix sorted
let p = 0, q = seen.length;
while (p < q) { const m = (p + q) >> 1; if (seen[m] < prefix) p = m + 1; else q = m; }
seen.splice(p, 0, prefix);
}
}
}
return best;
}class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int rows = matrix.length, cols = matrix[0].length;
int best = Integer.MIN_VALUE;
for (int l = 0; l < cols; l++) {
int[] colSums = new int[rows];
for (int r = l; r < cols; r++) {
for (int i = 0; i < rows; i++) colSums[i] += matrix[i][r];
TreeSet<Integer> seen = new TreeSet<>();
seen.add(0);
int prefix = 0;
for (int v : colSums) {
prefix += v;
Integer s = seen.ceiling(prefix - k);
if (s != null) best = Math.max(best, prefix - s);
seen.add(prefix);
}
}
}
return best;
}
}int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int rows = matrix.size(), cols = matrix[0].size();
int best = INT_MIN;
for (int l = 0; l < cols; l++) {
vector<int> colSums(rows, 0);
for (int r = l; r < cols; r++) {
for (int i = 0; i < rows; i++) colSums[i] += matrix[i][r];
set<int> seen{0};
int prefix = 0;
for (int v : colSums) {
prefix += v;
auto it = seen.lower_bound(prefix - k);
if (it != seen.end()) best = max(best, prefix - *it);
seen.insert(prefix);
}
}
}
return best;
}Explanation
A rectangle is defined by a left column, a right column, and a top/bottom row range. The big idea is to fix the left and right columns, squash everything between them into a single 1-D array of row sums, and then solve a simpler 1-D problem on it.
For each pair (l, r) we keep a running col_sums array where col_sums[i] is the sum of row i from column l to r. As r moves right, we just add the new column in, so this stays cheap.
Now on that 1-D array we want the best contiguous chunk whose sum is ≤ k. Using prefix sums, a chunk's sum is prefix - earlier_prefix. To make it as large as possible without exceeding k, for the current prefix we look for the smallest earlier prefix that is >= prefix - k — a binary search in a sorted set of seen prefixes.
This works because subtracting the smallest qualifying prefix gives the biggest valid sum that still respects the ≤ k limit. We track the best such value across all column pairs.
Example: for [[1,0,1],[0,-2,3]] with k = 2, scanning column pairs and probing prefixes finds a sub-rectangle summing to exactly 2, which is the answer.