363. Max Sum of Rectangle No Larger Than K - cocoder39/coco39_LC GitHub Wiki

363. Max Sum of Rectangle No Larger Than K

Notes 2020:

unfair for python user since there is no tree set in Python.

1D version mentioned below is straightforward. However, it requires some thoughts to convert the idea to 2D version.

Time complexity is O(m^2 * n log(n)) where m = max(row, col) and n = min(row, col)

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        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);
        boolean isColBigger = col >= row;
        int diff = Integer.MIN_VALUE;
        
        for (int i = 0; i < m; i++) {
            int[] dp = new int[n];
            for (int j = i; j < m; j++) {
                TreeSet<Integer> treeSet = new TreeSet<Integer>();
                treeSet.add(0);
                int cumulative_sum = 0;
                for (int a = 0; a < n; a++) {
                    dp[a] += (isColBigger ? matrix[j][a] : matrix[a][j]);
                    cumulative_sum += dp[a];
                    
                    // the least element greater than or equal to input value
                    // or null if there is no such element.
                    Integer candidate = treeSet.ceiling(cumulative_sum-k);
                    if (candidate != null) {
                        diff = Math.max(diff, cumulative_sum-candidate);
                    }
                    treeSet.add(cumulative_sum);
                }
            }
        }
        return diff; 
    }
}

========================================================================

take this leetcode discussion as reference.

a naive idea is brute-force with enumerating left, right, top, bottom bound of the rectangle, of which the time complexity is O(m^2 * n^2).

There is a simpler 1D version of this problem max subarray subject to that sum is less than k

first, we want the sum of a range [i, j], which is sum[j] - sum[i] < k. we use upper_bound to get a sum which is > sum[j] - k by looking up sums from a set, check if it can make the range sum closer to k.

int best_cumulative_sum(int ar[],int N,int K)
{
    set<int> cumset;
    cumset.insert(0);
    int best=0,cum=0;
    for(int i=0;i<N;i++)
    {
        cum+=ar[i];
        set<int>::iterator sit=cumset.upper_bound(cum-K);
        if(sit!=cumset.end())best=max(best,cum-*sit);
        cumset.insert(cum);
    }
    return best;
}

where set::lower_bound is utilized, thus the time complexity is O(n * log n) where n is the size of array. By taking advantage of idea from the 1d version, the problem can be optimized to O(n^2 * m * log m) where n < m (if not, swap them)

int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();
        int dist = INT_MAX;
        int res = 0;
        
        for (int left = 0; left < n; left++) {
            vector<int> sumRows(m); // each element is sum within a row from [i][left] to [i][right]
            for (int right = left; right < n; right++) {
                int cum = 0;
                set<int> st;
                st.insert(0);
                for (int i = 0; i < m; i++) {
                    sumRows[i] += matrix[i][right]; //sum of matrix from [i][left] to [i][right]
                    cum += sumRows[i]; //sum of matrix from [0, 0] to [i][right]
                    auto it = st.lower_bound(cum - k); //*it >= cum - k
                    if (it != st.end() && dist > k - (cum - *it)) {
                        res = cum - *it;
                        dist = k - res;
                    }
                    st.insert(cum);
                }
            }
        }
        return res;
    }

int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();
        bool col_orient = true;
        if (n > m) {
            swap(m, n);
            col_orient = false;
        }
        
        int res = INT_MIN;
        for (int left = 0; left < n; left++) {
            vector<int> row_sums(m);
            for (int right = left; right < n; right++) {
                for (int row = 0; row < m; row++) {
                    row_sums[row] += col_orient ? matrix[row][right] : matrix[right][row];
                }
                
                set<int> accus;
                accus.insert(0);
                int accu = 0, max_accu = INT_MIN;
                for (int row = 0; row < m; row++) {
                    accu += row_sums[row];
                    auto it = accus.lower_bound(accu - k); //*it >= accu - k
                    if (it != accus.end()) {
                        max_accu = max(max_accu, accu - *it);
                    }
                    accus.insert(accu);
                }
                res = max(res, max_accu);
            }
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️