Max Sum of Rectangle No Larger Than K — Problem & Solution
Max Sum of Rectangle No Larger Than K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Max Sum of Rectangle No Larger Than K is a hard coding problem on arrays, binary search and matrix, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Binary Search, Matrix, Ordered Set
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an m x n integer matrix matrix and an integer k, consider every non-empty axis-aligned rectangle of cells inside the matrix. Return the largest rectangle sum that is no larger than k.
The input guarantees that at least one rectangle has a sum <= k.
Example 1
Input: matrix = [[2,-1,3],[-4,5,1]], k = 4
Output: 4
Explanation: The whole first row sums to 2 - 1 + 3 = 4, the largest value allowed. The column `[3,1]` sums to 4 as well.
Example 2
Input: matrix = [[3,3,-1]], k = 5
Output: 5
Explanation: `[3,3,-1]` sums to 5; `[3,3]` sums to 6, which is too large.
Example 3
Input: matrix = [[5,-2],[-1,4]], k = 0
Output: -1
Constraints
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-100 <= matrix[i][j] <= 100-10^5 <= k <= 10^5
Follow-up: What if the number of rows is much larger than the number of columns?
Hints for Max Sum of Rectangle No Larger Than K
Hint 1
Fix a top row and a bottom row. Squashing the band between them into one array of column sums turns the problem into a 1D one.
Hint 2
In 1D: the sum of
cols[i+1..j]isprefix[j] - prefix[i]. You want the largest such difference that is<= k.Hint 3
Scan the prefixes left to right and keep the earlier ones in a sorted structure; for
prefix[j], the best partner is the smallest earlier prefix that is>= prefix[j] - k.
How to solve Max Sum of Rectangle No Larger Than K
Reduce to 1D by fixing the row band, then answer "max subarray sum <= k" with prefix sums and an ordered set — the smallest earlier prefix that is at least prefix - k gives the best subarray ending here.
Approach
- For every pair of rows
top <= bottom, maintaincols[c]= the sum of columncbetween them (add rowbottomas it grows). - Start a sorted set holding the empty prefix
0and a running prefixp = 0. - For each column, add
cols[c]top; find the smallestqin the set withq >= p - k. If it exists,p - qis a candidate — keep the maximum. - Insert
pinto the set and continue. Stop early if the answer ever equalsk.
Why it works
Every rectangle is a row band plus a column range, and every column range's sum is a difference of two prefixes of the band's column sums. For a fixed right end the difference p - q is largest when q is smallest, subject to p - q <= k, i.e. q >= p - k — exactly the ceiling query. So every rectangle is considered implicitly and the best valid one is found.
Complexity
- Time —
O(m² · n log n) - Space —
O(n)
Pitfalls
- Kadane's algorithm finds the maximum subarray but cannot respect the
<= kcap — the ordered-set search is what handles it. - Seed the set with
0, or subarrays that start at the first column are missed. - The answer can be negative; do not initialise the best value with 0.
Reference solution
Python
from typing import List
import bisect
def maxSumSubmatrix(matrix: List[List[int]], k: int) -> int:
m, n = len(matrix), len(matrix[0])
best = None
for top in range(m):
cols = [0] * n
for bottom in range(top, m):
row = matrix[bottom]
for c in range(n):
cols[c] += row[c]
seen = [0]
prefix = 0
for v in cols:
prefix += v
i = bisect.bisect_left(seen, prefix - k)
if i < len(seen):
cand = prefix - seen[i]
if best is None or cand > best:
best = cand
bisect.insort(seen, prefix)
if best == k:
return k
return bestJava
public static int maxSumSubmatrix(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
int best = Integer.MIN_VALUE;
for (int top = 0; top < m; top++) {
int[] cols = new int[n];
for (int bottom = top; bottom < m; bottom++) {
for (int c = 0; c < n; c++) cols[c] += matrix[bottom][c];
TreeSet<Integer> seen = new TreeSet<>();
seen.add(0);
int prefix = 0;
for (int c = 0; c < n; c++) {
prefix += cols[c];
Integer q = seen.ceiling(prefix - k);
if (q != null) best = Math.max(best, prefix - q);
seen.add(prefix);
}
if (best == k) return k;
}
}
return best;
}C++
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int m = matrix.size(), n = matrix[0].size();
int best = INT_MIN;
for (int top = 0; top < m; top++) {
vector<int> cols(n, 0);
for (int bottom = top; bottom < m; bottom++) {
for (int c = 0; c < n; c++) cols[c] += matrix[bottom][c];
set<int> seen;
seen.insert(0);
int prefix = 0;
for (int c = 0; c < n; c++) {
prefix += cols[c];
auto it = seen.lower_bound(prefix - k);
if (it != seen.end()) best = max(best, prefix - *it);
seen.insert(prefix);
}
if (best == k) return k;
}
}
return best;
}JavaScript
var maxSumSubmatrix = function(matrix, k) {
var m = matrix.length, n = matrix[0].length, best = -Infinity;
var lowerBound = function(a, x) {
var lo = 0, hi = a.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (a[mid] < x) lo = mid + 1; else hi = mid;
}
return lo;
};
for (var top = 0; top < m; top++) {
var cols = new Array(n).fill(0);
for (var bottom = top; bottom < m; bottom++) {
for (var c = 0; c < n; c++) cols[c] += matrix[bottom][c];
var seen = [0], prefix = 0;
for (var j = 0; j < n; j++) {
prefix += cols[j];
var i = lowerBound(seen, prefix - k);
if (i < seen.length && prefix - seen[i] > best) best = prefix - seen[i];
seen.splice(lowerBound(seen, prefix), 0, prefix);
}
if (best === k) return k;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search