Java Binary Search solution time complexity min(m,n)^2*max(m,n)*log(max(m,n))

• ``````/* 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>();
//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;
}``````

• This post is deleted!

Can you explain why you need to set.add(0) ?? even though s(j) (j < i) may not necessarily contains 0?

Many thanks!

• 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.

• Thanks for your answer! Could explain that why the subres is the ceiling of val-target not target-val? and why the res is the val - subres? Thanks very much!

• Assume val is sum from 0~k, we want to find an index t (t<k) (assume sum from 0~t is subres) so that val-subres<=target, thus subres>=val-target, which is set.ceiling(val-target).

• I see. Thanks very much!

• Assume the matrix is [[1,2,3],[1,2,3]], are the vals is treeset 1,3,6, 2,7,16? Assume k is 5, the sum of [2,3] in first and second row both satisfies. The [2,3] in first row is found by 6-1, but how is the [2,3] in the second row is found?

• @codebitch think this [[5]] 5

• l = val + array[k];

Thanks for your idea.In a 1D matrix,why the time complex is O(nlogn)? I think the sum array is not sorted because of the negative number,so we can't do a binary search directly.

• This post is deleted!

• @futurehau I think the time complexity is nlog(n).

• @futurehau Because the sum is added to a treeset， i think this step finished the sorting process.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.