Max Sum of Rectangle No Larger Than K – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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 <= 200-100 <= matrix[i][j] <= 100-105 <= k <= 105
C++ Max Sum of Rectangle No Larger Than K LeetCode Solution
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
if (matrix.empty()) return 0;
int row = matrix.size(), col = matrix[0].size(), res = INT_MIN;
for (int l = 0; l < col; ++l) {
vector<int> sums(row, 0);
for (int r = l; r < col; ++r) {
for (int i = 0; i < row; ++i) {
sums[i] += matrix[i][r];
}
// Find the max subarray no more than K
set<int> accuSet;
accuSet.insert(0);
int curSum = 0, curMax = INT_MIN;
for (int sum : sums) {
curSum += sum;
set<int>::iterator it = accuSet.lower_bound(curSum - k);
if (it != accuSet.end()) curMax = std::max(curMax, curSum - *it);
accuSet.insert(curSum);
}
res = std::max(res, curMax);
}
}
return res;
}
Java Max Sum of Rectangle No Larger Than K LeetCode Solution
public int maxSumSubmatrix(int[][] matrix, int target) {
int row = matrix.length;
if(row==0)return 0;
int col = matrix[0].length;
int m = Math.min(row,col);
int n = Math.max(row,col);
//indicating sum up in every row or every column
boolean colIsBig = col>row;
int res = Integer.MIN_VALUE;
for(int i = 0;i<m;i++){
int[] array = new int[n];
// sum from row j to row i
for(int j = i;j>=0;j--){
int val = 0;
TreeSet<Integer> set = new TreeSet<Integer>();
set.add(0);
//traverse every column/row and sum up
for(int k = 0;k<n;k++){
array[k]=array[k]+(colIsBig?matrix[j][k]:matrix[k][j]);
val = val + array[k];
//use TreeMap to binary search previous sum to get possible result
Integer subres = set.ceiling(val-target);
if(null!=subres){
res=Math.max(res,val-subres);
}
set.add(val);
}
}
}
return res;
}
Python 3 Max Sum of Rectangle No Larger Than K LeetCode Solution
For each row, calculate the prefix sum. For each pair of columns, calculate the sum of rows.
Now this problem is changed to a 1D problem: max subarray sum no more than k.
def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
def maxSumSubarray(arr):
sub_s_max = float('-inf')
s_curr = 0
prefix_sums = [float('inf')]
for x in arr:
bisect.insort(prefix_sums, s_curr)
s_curr += x
i = bisect.bisect_left(prefix_sums, s_curr - k)
sub_s_max = max(sub_s_max, s_curr - prefix_sums[i])
return sub_s_max
m, n = len(matrix), len(matrix[0])
for x in range(m):
for y in range(n - 1):
matrix[x][y+1] += matrix[x][y]
res = float('-inf')
for y1 in range(n):
for y2 in range(y1, n):
arr = [matrix[x][y2] - (matrix[x][y1-1] if y1 > 0 else 0) for x in range(m)]
res = max(res, maxSumSubarray(arr))
return res
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
