363. Max Sum of Rectangle No Larger Than K LeetCode Solution
In this guide, you will get 363. Max Sum of Rectangle No Larger Than K LeetCode Solution with the best time and space complexity. The solution to Max Sum of Rectangle No Larger Than K problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Max Sum of Rectangle No Larger Than K
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.length
n == matrix[i].length
1 <= 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?
Complexity Analysis
Time Complexity: O(\min(m, n)^2 \cdot \max(m, n) \cdot \log\max(m, n))
363. Max Sum of Rectangle No Larger Than K LeetCode Solution in C++
class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
const int m = matrix.size();
const int n = matrix[0].size();
int ans = INT_MIN;
for (int baseCol = 0; baseCol < n; ++baseCol) {
// sums[i] := sum(matrix[i][baseCol..j])
vector<int> sums(m, 0);
for (int j = baseCol; j < n; ++j) {
for (int i = 0; i < m; ++i)
sums[i] += matrix[i][j];
// Find the maximum sum <= k of all the subarrays.
set<int> accumulate{0};
int prefix = 0;
for (const int sum : sums) {
prefix += sum;
if (const auto it = accumulate.lower_bound(prefix - k);
it != accumulate.cend())
ans = max(ans, prefix - *it);
accumulate.insert(prefix);
}
}
}
return ans;
}
}; /* code provided by PROGIEZ */
363. Max Sum of Rectangle No Larger Than K LeetCode Solution in Java
class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
final int m = matrix.length;
final int n = matrix[0].length;
int ans = Integer.MIN_VALUE;
for (int baseCol = 0; baseCol < n; ++baseCol) {
// sums[i] := sum(matrix[i][baseCol..j])
int[] sums = new int[m];
for (int j = baseCol; j < n; ++j) {
for (int i = 0; i < m; ++i)
sums[i] += matrix[i][j];
// Find the maximum sum <= k of all the subarrays.
TreeSet<Integer> accumulate = new TreeSet<>(Arrays.asList(0));
int prefix = 0;
for (final int sum : sums) {
prefix += sum;
final Integer lo = accumulate.ceiling(prefix - k);
if (lo != null)
ans = Math.max(ans, prefix - lo);
accumulate.add(prefix);
}
}
}
return ans;
}
} // code provided by PROGIEZ
363. Max Sum of Rectangle No Larger Than K LeetCode Solution in Python
from sortedcontainers import SortedList
class Solution:
def maxSumSubmatrix(self, matrix: list[list[int]], k: int) -> int:
m = len(matrix)
n = len(matrix[0])
ans = -math.inf
for baseCol in range(n):
# sums[i] := sum(matrix[i][baseCol..j])
sums = [0] * m
for j in range(baseCol, n):
for i in range(m):
sums[i] += matrix[i][j]
# Find the maximum sum <= k of all the subarrays.
accumulate = SortedList([0])
prefix = 0
for summ in sums:
prefix += summ
it = accumulate.bisect_left(prefix - k)
if it != len(accumulate):
ans = max(ans, prefix - accumulate[it])
accumulate.add(prefix)
return ans # code by PROGIEZ
