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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

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