Max Sum of Rectangle No Larger Than K -- Leetcode

Question:

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?

Answer:
Solution:
Binary Search. Time:O(m*m*n*logn) , m<n

    public int maxSumSubmatrix(int[][] matrix, int k) {

        if(matrix==null || matrix.length==0)return 0;
        int m = matrix.length;
        if(matrix[0]==null || matrix[0].length==0)return 0;
        int n = matrix[0].length;
        int max = Integer.MIN_VALUE;
       //ensure m <= n
        boolean flag = m <= n ? true : false;
        if(!flag){
            int tmp = n;
            n = m;
            m = tmp;
        }
       
        for(int start=0;start<m;start++){
            int[] col = new int[n];
            TreeSet<Integer> set = new TreeSet<Integer>();
           
            for(int i=start;i<m;i++){
                set.clear();
                int colSum = 0;
                set.add(colSum);
               
                for(int j=0;j<n;j++){
                    if(flag){
                        col[j] += matrix[i][j];
                    }else{
                        col[j] += matrix[j][i];
                    }
                    colSum += col[j];
                   
                    //colSum - x <= k --> colSum - k <= x
                    //TreeSet binary search: O(logn)!  If treeSet cannot find a ceiling ele of (colSum - k), return NULL!
                    if(set.ceiling(colSum - k) != null){
                        int ceiling = set.ceiling(colSum - k);
                        int maxCur = colSum - ceiling;
                        max = Math.max(max, maxCur);
                    }
                    set.add(colSum);
                }
            }
        }
        return max;
    }