Thursday, June 23, 2016

LeetCode 363 - Max Sum of Rectangle No Larger Than K

https://leetcode.com/problems/max-sum-of-sub-matrix-no-larger-than-k/
Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.
Example:
```Given matrix = [
[1,  0, 1],
[0, -2, 3]
]
k = 2
```
The answer is `2`. Because the sum of rectangle `[[0, 1], [-2, 3]]` is 2 and 2 is the max number no larger than k (k = 2).
Note:
1. The rectangle inside the matrix must have an area > 0.
2. What if the number of rows is much larger than the number of columns?
https://discuss.leetcode.com/topic/48875/accepted-c-codes-with-explanation-and-references
The naive solution is brute-force, which is O((mn)^2). In order to be more efficient, I tried something similar to Kadane's algorithm. The only difference is that here we have upper bound restriction K. Here's the easily understanding video link for the problem "find the max sum rectangle in 2D array": Maximum Sum Rectangular Submatrix in Matrix dynamic programming/2D kadane (Trust me, it's really easy and straightforward).
Once you are clear how to solve the above problem, the next step is to find the max sum no more than K in an array. This can be done within O(nlogn), and you can refer to this article: max subarray sum no more than k.
For the solution below, I assume that the number of rows is larger than the number of columns. Thus in general time complexity is O[min(m,n)^2 * max(m,n) * log(max(m,n))], space O(max(m, n)).
``````public int maxSumSubmatrix(int[][] matrix, int k) {
//2D Kadane's algorithm + 1D maxSum problem with sum limit k
//2D subarray sum solution

//boundary check
if(matrix.length == 0) return 0;

int m = matrix.length, n = matrix[0].length;
int result = Integer.MIN_VALUE;

//outer loop should use smaller axis
//now we assume we have more rows than cols, therefore outer loop will be based on cols
for(int left = 0; left < n; left++){
//array that accumulate sums for each row from left to right
int[] sums = new int[m];
for(int right = left; right < n; right++){
//update sums[] to include values in curr right col
for(int i = 0; i < m; i++){
sums[i] += matrix[i][right];
}

//we use TreeSet to help us find the rectangle with maxSum <= k with O(logN) time
TreeSet<Integer> set = new TreeSet<Integer>();
//add 0 to cover the single row case
int currSum = 0;

for(int sum : sums){
currSum += sum;
//we use sum subtraction (curSum - sum) to get the subarray with sum <= k
//therefore we need to look for the smallest sum >= currSum - k
Integer num = set.ceiling(currSum - k);//\\
if(num != null) result = Math.max( result, currSum - num );
}
}
}

return result;
}``````
https://discuss.leetcode.com/topic/48854/java-binary-search-solution-time-complexity-min-m-n-2-max-m-n-log-max-m-n
``````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>();
//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);
}
}
}
}
return res;
}``````

`sums[i] = Σ(matrix[i][x..y])`

public int maxSumSubmatrix(int[][] matrix, int k) { int m = matrix.length, n = 0; if (m > 0) n = matrix[0].length; if (m * n == 0) return 0; int M = Math.max(m, n); int N = Math.min(m, n); int ans = Integer.MIN_VALUE; for (int x = 0; x < N; x++) { int sums[] = new int[M]; for (int y = x; y < N; y++) { TreeSet<Integer> set = new TreeSet<Integer>(); int num = 0; for (int z = 0; z < M; z++) { sums[z] += m > n ? matrix[z][y] : matrix[y][z]; num += sums[z]; if (num <= k) ans = Math.max(ans, num); Integer i = set.ceiling(num - k); if (i != null) ans = Math.max(ans, num - i); set.add(num); } } } return ans; }
https://www.hrwhisper.me/leetcode-max-sum-rectangle-no-larger-k/

[1, 0, 1],
[0, -2, 3]

int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
if (matrix.empty()) return 0;
int ans = INT_MIN,m = matrix.size(), n = matrix[0].size(),row_first=true;
if (m > n) {
swap(m, n);
row_first = false;
}
for (int ri = 0; ri < m; ri++) {
vector<int> temp(n, 0);
for (int i = ri; i >= 0; i--) {
set<int> sums;
int sum = 0;
sums.insert(sum);
for (int j = 0; j < n; j++) {
temp[j] += row_first ? matrix[i][j]: matrix[j][i];
sum += temp[j];
auto it = sums.lower_bound(sum - k);
if (it != sums.end())
ans = max(ans, sum - *it);
sums.insert(sum);
}
}
}
return ans;
}
https://leetcode.com/discuss/109705/java-binary-search-solution-time-complexity-min-max-log-max
/* first consider the situation matrix is 1D we can save every sum of 0~i(0<=i<len) and binary search previous sum to find possible result for every index, time complexity is O(NlogN). so in 2D matrix, we can sum up all values from row i to row j and create a 1D array to use 1D array solution. If col number is less than row number, we can sum up all values from col i to col j then use 1D array 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; }
Thank you for your great answer! Can you explain why you need to set.add(0) ?? even though s(j) (j < i) may not necessarily contains 0?
Because the result can start from index 0. e.g. [1,1,5] k=3 solution is 1+1=2. So 0 in set means no need to subtract previous sum.
There is a simple version of O(n^4). The idea is to calculate every rectangle [[r1,c1], [r2,c2]], and simply pick the max area <= k. An improved version takes O(n^3logn). It borrows the idea to find max subarray with sum <= k in 1D array, and apply here: we find all rectangles bounded between r1 & r2, with columns from 0 to end. Pick a pair from tree. I remember the interviewer said there could be an even better solution, but I haven't figured that out...
public int maxSumSubmatrix(int[][] matrix, int k) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; int rows = matrix.length, cols = matrix[0].length; int[][] areas = new int[rows][cols]; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { int area = matrix[r][c]; if (r-1 >= 0) area += areas[r-1][c]; if (c-1 >= 0) area += areas[r][c-1]; if (r-1 >= 0 && c-1 >= 0) area -= areas[r-1][c-1]; areas[r][c] = area; } } int max = Integer.MIN_VALUE; for (int r1 = 0; r1 < rows; r1++) { for (int c1 = 0; c1 < cols; c1++) { for (int r2 = r1; r2 < rows; r2++) { for (int c2 = c1; c2 < cols; c2++) { int area = areas[r2][c2]; if (r1-1 >= 0) area -= areas[r1-1][c2]; if (c1-1 >= 0) area -= areas[r2][c1-1]; if (r1-1 >= 0 && c1 -1 >= 0) area += areas[r1-1][c1-1]; if (area <= k) max = Math.max(max, area); } } } } return max; }
Solution II (O(n^3logn)
public int maxSumSubmatrix(int[][] matrix, int k) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; int rows = matrix.length, cols = matrix[0].length; int[][] areas = new int[rows][cols]; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { int area = matrix[r][c]; if (r-1 >= 0) area += areas[r-1][c]; if (c-1 >= 0) area += areas[r][c-1]; if (r-1 >= 0 && c-1 >= 0) area -= areas[r-1][c-1]; areas[r][c] = area; } } int max = Integer.MIN_VALUE; for (int r1 = 0; r1 < rows; r1++) { for (int r2 = r1; r2 < rows; r2++) { TreeSet<Integer> tree = new TreeSet<>(); tree.add(0); // padding for (int c = 0; c < cols; c++) { int area = areas[r2][c]; if (r1-1 >= 0) area -= areas[r1-1][c]; Integer ceiling = tree.ceiling(area - k); if (ceiling != null) max = Math.max(max, area - ceiling); tree.add(area); } } } return max; }

sums[j] – sums[i] <= k
sums[j] <= k + sums[i]

“满足小于等于k + sums[i]中最大的”  ==  floor(k + sums[i])

Red-Black Tree啊！TreeSet啊！TreeMap啊！Balanced Binary Search Tree啊！
[Time & Space]

`  ``public` `int` `maxSumSubmatrix(``int``[][] matrix, ``int` `k) {`
`    ``if` `(matrix == ``null` `|| matrix.length == ``0``) {`
`      ``return` `0``;`
`    ``}`
`    ``int` `m = matrix.length;`
`    ``int` `n = matrix[``0``].length;`
`    ``int` `result = Integer.MIN_VALUE;`
`    ``for` `(``int` `i = ``0``; i < n; i++) {`
`      ``int` `r = i;`
`      ``int``[] local = ``new` `int``[m];`
`      ``while` `(r < n) {`
`        ``for` `(``int` `x = ``0``; x < m; x++) {`
`          ``local[x] += matrix[x][r];`
`        ``}`
`        ``int` `localResult = maxSubArray(local, k);`
`        ``result = Math.max(result, localResult);`
`        ``r++;`
`      ``}`
`    ``}`
`    ``return` `result;`
`  ``}`
`  ``// maximum subarray less than k`
`  ``// can not use two pointer, [2, -7, 6, -1], k = 0`
`  ``// TreeSet, find ceiling, O(nlogn)`
`  ``private` `int` `maxSubArray(``int``[] nums, ``int` `k) {`
`    ``int` `result = Integer.MIN_VALUE;`
`    ``TreeSet<Integer> tSet = ``new` `TreeSet<>();`
`    ``int``[] sums = ``new` `int``[nums.length];`
`    ``sums[``0``] = nums[``0``];`
`    ``tSet.add(sums[``0``]);`
`    ``if` `(sums[``0``] <= k) {`
`      ``result = Math.max(result, sums[``0``]);`
`    ``}`
`    ``for` `(``int` `i = ``1``; i < nums.length; i++) {`
`      ``sums[i] = sums[i - ``1``] + nums[i];`
`      ``if` `(sums[i] <= k) {`
`        ``result = Math.max(result, sums[i]);`
`      ``}`
`      ``Integer ceil = tSet.ceiling(sums[i] - k);`
`      ``if` `(ceil != ``null``) {`
`        ``result = Math.max(result, sums[i] - ceil);`
`      ``}`
`      ``tSet.add(sums[i]);`
`    ``}`
`    ``return` `result;`
`  ``}`
`  ``// TreeSet find floor`
`  ``private` `int` `maxSubArray2(``int``[] nums, ``int` `k) {`
`    ``int` `n = nums.length;`
`    ``int` `result = Integer.MIN_VALUE;`
`    ``TreeSet<Integer> tSet = ``new` `TreeSet<>();`
`    ``int``[] sums = ``new` `int``[n];`
`    ``int` `sum = ``0``;`
`    ``for` `(``int` `i = ``0``; i < n; i++) {`
`      ``sum += nums[i];`
`    ``}`
`    ``for` `(``int` `i = n - ``1``; i >= ``0``; i--) {`
`      ``sums[i] = sum;`
`      ``if` `(sums[i] <= k) {`
`        ``result = Math.max(result, sums[i]);`
`      ``}`
`      ``if` `(i != n - ``1``) {`
`        ``Integer floor = tSet.floor(sums[i] + k);`
`        ``if` `(floor != ``null``) {`
`          ``result = Math.max(result, floor - sums[i]);`
`        ``}`
`      ``}`
`      ``sum -= nums[i];`
`      ``tSet.add(sums[i]);`
`    ``}`
`    ``return` `result;`
`  ``}`
X. Merge sort
https://discuss.leetcode.com/topic/53939/java-117ms-beat-99-81-merge-sort

`````` * If # of columns is smaller, process one set of columns [i..j) at a time, for each different i<j.
* For one set of colums [i..j), do it like "Count of Range Sum".
* O(n) = n^2 * mlogm.
* Assume we have such result.
public int maxSumSubmatrix(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length, ans = Integer.MIN_VALUE;
long[] sum = new long[m+1]; // stores sum of rect[0..p][i..j]
for (int i = 0; i < n; ++i) {
long[] sumInRow = new long[m];
for (int j = i; j < n; ++j) { // for each rect[*][i..j]
for (int p = 0; p < m; ++p) {
sumInRow[p] += matrix[p][j];
sum[p+1] = sum[p] + sumInRow[p];
}
ans = Math.max(ans, mergeSort(sum, 0, m+1, k));
if (ans == k) return k;
}
}
return ans;
}
int mergeSort(long[] sum, int start, int end, int k) {
if (end == start+1) return Integer.MIN_VALUE; // need at least 2 to proceed
int mid = start + (end - start)/2, cnt = 0;
int ans = mergeSort(sum, start, mid, k);
if (ans == k) return k;
ans = Math.max(ans, mergeSort(sum, mid, end, k));
if (ans == k) return k;
long[] cache = new long[end-start];
for (int i = start, j = mid, p = mid; i < mid; ++i) {
while (j < end && sum[j] - sum[i] <= k) ++j;
if (j-1 >= mid) {
ans = Math.max(ans, (int)(sum[j-1] - sum[i]));
if (ans == k) return k;
}
while (p < end && sum[p] < sum[i]) cache[cnt++] = sum[p++];
cache[cnt++] = sum[i];
}
System.arraycopy(cache, 0, sum, start, cnt);
return ans;
}``````

X. Brute Force
https://discuss.leetcode.com/topic/48923/2-accepted-java-solution
https://discuss.leetcode.com/topic/49083/naive-but-accepted-java-solution
There is a simple version of O(n^4).
The idea is to calculate every rectangle [[r1,c1], [r2,c2]], and simply pick the max area <= k.
An improved version takes O(n^3logn). It borrows the idea to find max subarray with sum <= k in 1D array, and apply here: we find all rectangles bounded between r1 & r2, with columns from 0 to end. Pick a pair from tree.
``````public int maxSumSubmatrix(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return 0;
int rows = matrix.length, cols = matrix[0].length;
int[][] areas = new int[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
int area = matrix[r][c];
if (r-1 >= 0)
area += areas[r-1][c];
if (c-1 >= 0)
area += areas[r][c-1];
if (r-1 >= 0 && c-1 >= 0)
area -= areas[r-1][c-1];
areas[r][c] = area;
}
}
int max = Integer.MIN_VALUE;
for (int r1 = 0; r1 < rows; r1++) {
for (int c1 = 0; c1 < cols; c1++) {
for (int r2 = r1; r2 < rows; r2++) {
for (int c2 = c1; c2 < cols; c2++) {
int area = areas[r2][c2];
if (r1-1 >= 0)
area -= areas[r1-1][c2];
if (c1-1 >= 0)
area -= areas[r2][c1-1];
if (r1-1 >= 0 && c1 -1 >= 0)
area += areas[r1-1][c1-1];
if (area <= k)
max = Math.max(max, area);
}
}
}
}
return max;
}``````