Shed some light on this typical solution in C++


  • 1

    Solution

    The most direct method is to test each possible rectangle in the matrix which will require O(n^4). Then can we do better? As we have done in one dimension array using prefix-sum, actually we can also follow that rule in two-dimension matrix:

    • start from the very leftmost (the first column) till the end
    • try each width till the very rightmost (the last column)
    • calculate the prefix-sum for each row then the partial sum can be easily retrieved as one-dimension situation
    • from the top to the bottom, collect the prefix-sum of each row then we can get the prefix-sum of the rectangle
    • use a set to store the prefix-sum of the rectangles and then searching curSum-k via lower_bound to retrieve so-called Max Sum of Rectangle No Larger Than K; as a result the whole time cost will be O(n^3*logn) now instead of O(n^4)
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) 
    {
            if(matrix.empty()) return 0;
            int rowSize = matrix.size(), colSize = matrix[0].size();
            int ret = INT_MIN;
            for(int l = 0; l < colSize; ++l) 
            {
                vector<int> sums(rowSize, 0); 
                for(int c = l; c < colSize; ++c) 
                {
                    for(int r = 0; r < rowSize; ++r) 
                        sums[r] += matrix[r][c];
                    set<int> sums_set; 
                    sums_set.insert(0); 
                    int maxSum = INT_MIN, sum = 0;
                    for(int i = 0; i < rowSize; ++i)
                    {
                        sum += sums[i]; 
                        auto iter = sums_set.lower_bound(sum-k); 
                        if(iter != sums_set.end()) maxSum = max(maxSum, sum-*iter); 
                        sums_set.insert(sum);
                    }
                    ret = max(ret, maxSum);
                }
            }
            return ret;
    }
    

    Always welcome new ideas and practical tricks, just leave them in the comments!


Log in to reply
 

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