Max Sum of Rectangle No Larger Than K
Hard · Sliding Window · Array · Binary Search · Matrix · Prefix Sum · Ordered Set
Problem
Given an m x n integer matrix matrix and an integer k, consider every axis-aligned sub-rectangle: any contiguous block of rows combined with any contiguous block of columns.
Return the largest rectangle sum that is at most k. The input guarantees that at least one rectangle sums to k or less.
Examples
Input: matrix = [[2,-1],[0,3]], k = 3 Output: 3
The single cell 3 hits the limit exactly. The whole matrix sums to 4, which is too large.
Input: matrix = [[5,-2,1]], k = 4 Output: 4
The whole row sums to 4, which is allowed, while the cell 5 alone is too large.
Constraints
- m == len(matrix), n == len(matrix[i])
- 1 <= m, n <= 100
- -100 <= matrix[i][j] <= 100
- -10^5 <= k <= 10^5
- At least one rectangle sums to k or less
Approaches
- Baseline: every rectangle from 2-D prefix sums — time O(m² · n²), space O(m · n)
Follow-up
What if the matrix has far more rows than columns? Run the bands over the columns instead, so the expensive part is quadratic in the short side. And without the cap, Kadane's algorithm replaces the sorted set: see the use cases “Largest subarray sum not above k” and “Largest rectangle sum, no limit”.
Related problems
Start free on Cariara · Coding problems · System design studio
