Leetcode 363. Max Sum of Rectangle No Larger Than K

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:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2 
Explanation: 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?

Analysis:

The naive solution would be for each sub-matrix of the matrix, we calculate the sum. We compare with k and get a largest one. Since we can do a presum of the matrix before, so getting the sum of the sub-matrix is O(1) operation. The total time complexity of the solution would be O(m * n * m * n).

A better solution:

Think about the 1D problem: If given a array of nums and target k, how can we get the max sum of the subarray of which its sum is no greater than k? 

The solution is do a presum of the array first, and for each number sum[i], our goal is to find out a sum[j], where sum[i] - sum[j] <= k, In other words,

sum[j] >= sum[i] - k.

Since our goal is to find out the sum cloest to k, here sum[j] should be the smallest number in sum and it's greater or equal to sum[i] - k.

We can use a treeset to store the previous sum[i]. Treeset provides a convenient function called ceiling(val) which returns the smallest number greater or equal to val in the treeSet. So our target is to find out the ceiling of (sum[i] - k).

Overall, the time complexity of the 1D array is O(n * logn).

Then let's go back to the 2-D matrix problem. We can choose any two of the columns, c1 and c2. And do a presum between c1 and c2. Then the 2D problem can be reduced to 1D. 

The overall time complexity is O(n^2 * m * logm). If n >> m, we can do a row-order presum first, find out two rows r1 and r2, do a presum between r1 and r2.

Code (Java):

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        int[][] preSum = new int[m][n + 1];
        
        for (int i = 0; i < m; i++) {
            for (int j = 1; j <= n; j++) {
                preSum[i][j] = preSum[i][j - 1] + matrix[i][j - 1];
            }
        }
        
        int ans = Integer.MIN_VALUE;
        for (int c1 = 1; c1 <= n; c1++) {
            for (int c2 = c1; c2 <= n; c2++) {
                int[] preSumRow = new int[m];
                for (int row = 0; row < m; row++) {
                    preSumRow[row] = preSum[row][c2] - preSum[row][c1 - 1];
                }
                
                ans = Math.max(ans, getMaxSubarrayHelper(preSumRow, k));
            }
        }
        
        return ans;
    }
    
    private int getMaxSubarrayHelper(int[] nums, int target) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        
        int ans = Integer.MIN_VALUE;
        int[] preSum = new int[nums.length + 1];
        
        for (int i = 1; i <= nums.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        
        treeSet.add(0);
        for (int i = 1; i <= nums.length; i++) {
            Integer num = preSum[i] - target;
            Integer ceiling = treeSet.ceiling(num);
            
            if (ceiling != null) {
                ans = Math.max(ans, preSum[i] - ceiling);
            }
            
            treeSet.add(preSum[i]);
        }
        
        return ans;
    }
}