Accepted C++ codes with explanation and references


  • 137

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

    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;
    }
    

  • 6
    A

    Why are you using lower_bound instead of upper bound ?


  • 3
    H

    sums[i,j] = sums[i] - sums[j].

    sums[i,j] is target subarray that needs to have sum <= k

    sums[j] is known current cumulative sum

    And we use binary search to find sums[i]. Therefore sums[i] needs to have sum >= sums[j] - k


  • 64
    H

    Good solution!

    Java version of this solution with my comments

    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
                set.add(0);
                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 );
                    set.add(currSum);
                }
            }
        }
        
        return result;
    }

  • 3
    V

    because the requirement is the sum of the subarray is "No larger than K" ,which means it can be equal. Using lower_bound gives the possbility of having the equal case included.


  • 0
    D

    Very good solution and thanks for sharing.

    Could you help elaborate a little why "I assume that the number of rows is larger than the number of columns "? Or what if the input data do not meet the assumption? Thanks


  • 2

    The important idea is to use dict to record the accumulated sum, so that we can calculate all the possible interval sum with the accumulated sum.
    sum[0..j] - {sum[0..0], sum[0,1], sum[0..k] }


  • 1

    In fact , I think it is really bad to use i,j,k letter as the parameter of the function as we typically choose these variable as the loop variable !!!

    I meet this fucking bug as I use k for loop logic as usual !!!!


  • 1

    Can anyone tell me why lower_bound() will use log(max(m,n)) complexity? Accumulative sum is not an ordered array, we cannot use binary search.


  • -2
    M
    This post is deleted!

  • 0
    M
    This post is deleted!

  • 0
    M
    This post is deleted!

  • 0

    @melouver Hey, that should be set::lower_bound :P
    Check it here: http://www.cplusplus.com/reference/set/set/lower_bound/


  • 0

    Here it's said, "Sets are typically implemented as binary search trees."
    http://www.cplusplus.com/reference/set/set/

    So before we check for upper or lower bound, the set will sort them first. So the insertions should generate a sorting lower bound nlogn here.
    If that's correct, this algorithm is worse than naive one because its complexity is
    max(m,n)^2 * min(m,n)^2 * log(min(m,n)) = (mn)^2logn

    I'm not sure, can anyone help?


  • 0

    Edit: Oops, I overlooked that @dfnjy posted twice and already had looked up the right place (std::set::lower_bound). No idea how you then went on to that misunderstanding about sets in your next post...


  • 0

    Oh I got one more n on previous post.
    So the double for loop will have min(m,n)^2 complexity, and set will provide max(m,n)log(max(m,n)) for sorting. Accumulative sum is sorted, everything is correct.
    Thank @melouver @StefanPochmann for replying.


  • 2
    F

    I wish everyone could post solutions like you did: Source code+explanation+links to references. Excellent!


  • 0
    M

    @hpplayer
    I think your version is contradicting with above C++ version, in here:
    in C++ version: it = accuSet.lower_bound(curSum - k);
    by definition of lower_bound, this is equivalent to: *it <= curSum -k => curSum - *it >= k, which is wrong because the question is asking for a sum (curSum - *it) no larger than k, that is curSum - *it <= k

    in your(Java) version: num = set.ceiling(currSum - k);
    by definition of ceiling, this is equivalent to: num >= currSum - k
    which is equivalent to: currSum - num <= k, which is right, because we want to find a maximum sum (currSum -num) no larger than k.

    However, I tried to run both version on online judgement, both of them passed, which is surprising.
    Are the test cases for C++ and Java++ the same?

    Or am I missing anything? Please advise.


  • 0
    M

    @java-chao said in Accepted C++ codes with explanation and references:

    accuSet

    I think your version is contradicting with below Java version by @hpplayer, in here:
    in C++ version: it = accuSet.lower_bound(curSum - k);
    by definition of lower_bound, this is equivalent to: *it <= curSum -k => curSum - *it >= k, which is wrong because the question is asking for a sum (curSum - *it) no larger than k, that is curSum - *it <= k

    in Java version: num = set.ceiling(currSum - k);
    by definition of ceiling, this is equivalent to: num >= currSum - k
    which is equivalent to: currSum - num <= k, which is right, because we want to find a maximum sum (currSum -num) no larger than k.

    However, I tried to run both version on online judgement, both of them passed, which is surprising.
    Are the test cases for C++ and Java++ the same?
    Do you think two solutions are contradicting with each other?

    Or am I missing anything? Please advise.


  • 0
    M

    I took my words back. I realized that
    In C++ a = set.lower_bound(t)
    In Java a = set.ceiling(t)

    Above are the same, both indicates: a >= t


Log in to reply
 

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