303. Max Sum of Rectangle No Larger Than K
You receive an m x n grid of integers matrix and an integer k. Consider every axis-aligned rectangle inside the grid — any contiguous block of rows combined with any contiguous block of columns. Each rectangle has a sum: the total of every cell it covers.
Return the largest rectangle sum that does not exceed k.
The input is guaranteed to contain at least one rectangle whose sum is at most k, so an answer always exists. Note that the best rectangle may be a single cell, a full row or column, or the entire grid.
Example 1:
Input: matrix = [[1, 0, 1], [0, -2, 3]], k = 2
Output: 2
Explanation: The 2×2 rectangle covering the last two columns holds 0, 1, -2, 3. Its sum is 2, which is the largest sum not exceeding k = 2.
Example 2:
Input: matrix = [[2, 2, -1]], k = 3
Output: 3
Explanation: Taking the whole row gives 2 + 2 + (-1) = 3, exactly k. No rectangle does better without going over.
Constraints:
- 1 ≤ m, n ≤ 100
- -100 ≤ matrix[i][j] ≤ 100
- -10⁵ ≤ k ≤ 10⁵
- At least one rectangle has a sum no larger than k.
Hints:
Every rectangle is pinned down by four boundaries: a top and bottom row, and a left and right column. A 2D prefix-sum table gives you any rectangle's sum in O(1) — that alone yields an O(m²n²) enumeration.
Fix the left and right column boundaries. Every rectangle between them is described by a range of rows, so the 2D problem collapses to: given a 1D array of row sums, find the best subarray sum ≤ k.
For the 1D problem, scan prefix sums left to right while keeping every earlier prefix in a sorted set. A subarray ending at position j has sum prefix[j] − prefix[i]; you want the smallest earlier prefix that is ≥ prefix[j] − k, which a sorted-set ceiling lookup (binary search) finds in O(log n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: matrix = [[1, 0, 1], [0, -2, 3]], k = 2
Expected output: 2