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


  • 47
    W
    /* 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;
    }

  • 0
    K
    This post is deleted!

  • 0
    C

    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?

    Many thanks!


  • 2
    W

    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.


  • 0
    Y

    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!


  • 2
    W

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


  • 0
    Y

    I see. Thanks very much!


  • 0
    S

    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?


  • 0
    F

    @codebitch think this [[5]] 5


  • 1
    F

    @wuzixigua said in Java Binary Search solution time complexity min(m,n)^2*max(m,n)*log(max(m,n)):

    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.


  • 0
    This post is deleted!

Log in to reply
 

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