Max Sum of Rectangle No Larger Than K
HardPrompt
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?
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves checking every possible rectangle within the matrix. To avoid re-calculating the sum of each rectangle from scratch, which would be very inefficient, we can pre-compute a 2D prefix sum array (also known as a summed-area table). This table allows us to find the sum of any rectangle in constant O(1) time.
Algorithm
-
- Create a
(m+1) x (n+1)prefix sum matrixsums.
- Create a
-
- Populate
sumsinO(m*n)time using the formula:sums[i][j] = matrix[i-1][j-1] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1].
- Populate
-
- Initialize
max_sum = Integer.MIN_VALUE.
- Initialize
-
- Use four nested loops to iterate through all possible top-left
(r1, c1)and bottom-right(r2, c2)corners of a rectangle.
- Use four nested loops to iterate through all possible top-left
-
- For each rectangle, calculate its sum in
O(1)using thesumsmatrix:current_sum = sums[r2+1][c2+1] - sums[r1][c2+1] - sums[r2+1][c1] + sums[r1][c1].
- For each rectangle, calculate its sum in
-
- If
current_sum <= k, updatemax_sum = Math.max(max_sum, current_sum).
- If
-
- Return
max_sum.
- Return
Walkthrough
First, we create a (m+1) x (n+1) prefix sum matrix, let's call it sums. sums[i][j] will store the sum of all elements in the rectangle from the top-left corner (0, 0) to (i-1, j-1). This sums matrix can be populated in O(m*n) time using a dynamic programming recurrence relation. After the sums matrix is built, we iterate through all possible rectangles. A rectangle is defined by its top-left corner (r1, c1) and its bottom-right corner (r2, c2). This requires four nested loops. For each rectangle, we calculate its sum in O(1) using the pre-computed sums matrix. If this sum is less than or equal to k, we compare it with our current maximum sum found so far and update it if the current sum is larger. We initialize the maximum sum to a very small number to handle negative matrix elements correctly. Since the problem guarantees a solution exists, we will always find a valid sum.
class Solution { public int maxSumSubmatrix(int[][] matrix, int k) { int rows = matrix.length; int cols = matrix[0].length; int[][] sums = new int[rows + 1][cols + 1]; for (int i = 1; i <= rows; i++) { for (int j = 1; j <= cols; j++) { sums[i][j] = matrix[i - 1][j - 1] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1]; } } int maxSum = Integer.MIN_VALUE; for (int r1 = 1; r1 <= rows; r1++) { for (int c1 = 1; c1 <= cols; c1++) { for (int r2 = r1; r2 <= rows; r2++) { for (int c2 = c1; c2 <= cols; c2++) { int currentSum = sums[r2][c2] - sums[r1 - 1][c2] - sums[r2][c1 - 1] + sums[r1 - 1][c1 - 1]; if (currentSum <= k) { maxSum = Math.max(maxSum, currentSum); } } } } } return maxSum; }}Complexity
Time
O(m^2 * n^2). The pre-computation of the sum matrix is `O(m*n)`, but this is dominated by the four nested loops required to define and check every possible rectangle.
Space
O(m * n) to store the 2D prefix sum matrix.
Trade-offs
Pros
Conceptually simpler to understand and implement than more optimal solutions.
Improves upon a naive
O(m^3 * n^3)brute-force approach by using prefix sums.
Cons
The time complexity is too high for the given constraints (
m, n <= 100), and this solution will likely result in a 'Time Limit Exceeded' error on most platforms.
Solutions
Solution
class Solution {public int maxSumSubmatrix(int[][] matrix, int k) { int m = matrix.length; int n = matrix[0].length; final int inf = 1 << 30; int ans = -inf; for (int i = 0; i < m; ++i) { int[] nums = new int[n]; for (int j = i; j < m; ++j) { for (int h = 0; h < n; ++h) { nums[h] += matrix[j][h]; } int s = 0; TreeSet<Integer> ts = new TreeSet<>(); ts.add(0); for (int x : nums) { s += x; Integer y = ts.ceiling(s - k); if (y != null) { ans = Math.max(ans, s - y); } ts.add(s); } } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.