Watch 10 video solutions for Max Sum of Rectangle No Larger Than K, a hard level problem involving Array, Binary Search, Matrix. This walkthrough by Coding Decoded has 13,072 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.
It is guaranteed that there will be a rectangle with a sum no larger than k.
Example 1:
Input: matrix = [[1,0,1],[0,-2,3]], k = 2 Output: 2 Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).
Example 2:
Input: matrix = [[2,2,-1]], k = 3 Output: 3
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-100 <= matrix[i][j] <= 100-105 <= k <= 105
Follow up: What if the number of rows is much larger than the number of columns?
Problem Overview: You are given a 2D matrix and an integer k. The task is to find the maximum possible sum of any rectangular submatrix such that the sum does not exceed k. The challenge comes from efficiently exploring all rectangle combinations without exceeding time limits.
Approach 1: Prefix Sum with Iteration (Brute Force Optimization) (O(m^2 * n^2) time, O(1) extra space)
Compute a prefix sum matrix so you can calculate any rectangle sum in constant time. Iterate over every possible pair of top-left and bottom-right coordinates. For each pair, compute the rectangle sum using the prefix matrix and track the largest value that does not exceed k. This removes repeated summations but still checks all rectangles, leading to quadratic choices for rows and columns.
Approach 2: Prefix Sum + Ordered Set with Binary Search (Optimal) (O(cols^2 * rows log rows) time, O(rows) space)
Fix two column boundaries and compress the rows between them into a 1D array of cumulative sums. The problem then becomes: find the maximum subarray sum no larger than k. Maintain prefix sums and store them in an ordered structure (like a balanced BST or TreeSet). For each running prefix sum s, search for the smallest prefix ≥ s - k using binary search. This guarantees the largest valid subarray sum ending at the current row. Repeat for every column pair. The ordered structure is the key insight that avoids checking every subarray.
Approach 3: Recursive Approach with Memoization (O(m * n * states) time, O(m * n) space)
A recursive formulation explores rectangle boundaries while caching intermediate sums using memoization. Each recursive call expands a rectangle by adjusting row or column limits and stores previously computed sums to avoid recomputation. While memoization reduces duplicate work, the state space still grows quickly for large matrices. This approach is mainly useful for conceptual understanding or smaller constraints rather than optimal performance.
Recommended for interviews: The prefix-sum + ordered set solution is the expected answer. Interviewers want to see how you reduce the 2D rectangle problem into a 1D subarray constraint and then solve it using prefix sums and an ordered set. Explaining the brute force prefix-sum approach first shows problem decomposition, while the ordered-set optimization demonstrates strong algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum with Iteration | O(m^2 * n^2) | O(1) | Simple implementation and good for understanding rectangle prefix sums |
| Prefix Sum + Ordered Set (Binary Search) | O(cols^2 * rows log rows) | O(rows) | Best general solution for large matrices and typical interview expectations |
| Recursive with Memoization | O(m * n * states) | O(m * n) | Useful for conceptual exploration or smaller input sizes |