Leetcode 363. Max Sum of Rectangle No Larger Than K

Problem Explanation

The maximum sum of rectangle no larger than K is often used in dynamic programming and involves the computation of the maximum sum of a subrectangle within a given 2D array. The sum of the subrectangle should not exceed a given integer value (k). In this case, the task is to find such a subrectangle in the 2D array such that its sum is no larger than k and is maximum.

For example, if our matrix is [[1,0,1],[0,-2,3]] and k = 2. The rectangle with the largest sum no larger than k is [[0,1],[-2,3]] providing the sum of 2.

Walkthrough of the Approach

This problem can be solved using a combination of dynamic programming and binary search.

The main idea behind the solution is to go through the array column by column and calculate the sum of each column to generate all the possible sub-rectangles in terms of column combinations. Then, we use set data structure from standard libraries in order to calculate the sum of the possible sub-arrays in a row.

At this point, we want to find a subarray for which the sum is closest to but not greater than the limit K. We use the function accumulate.lower_bound(prefix - k) to get an iterator pointing to the first element that is not less than prefix - k in the set.

Solution

Below is the implementation in C++, Java and Python language of the solution approach that was described above.

C++ Solution

1
2c++
3#include<vector>
4#include<set>
5using namespace std;
6
7class Solution {
8 public:
9  int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
10    const int m = matrix.size();
11    const int n = matrix[0].size();
12    int ans = INT_MIN;
13    for (int baseCol = 0; baseCol < n; baseCol++) {
14      vector<int> sums(m, 0);
15      for (int j = baseCol; j < n; j++) {
16        for (int i = 0; i < m; i++)
17          sums[i] += matrix[i][j];
18        set<int> accumulate{0};
19        int prefix = 0;
20        //Calculate the current sum and compare it with the optimal one
21        for (const int sum : sums) {
22          prefix += sum;
23          auto it = accumulate.lower_bound(prefix - k);
24          if (it != accumulate.end())
25            ans = max(ans, prefix - *it);
26          accumulate.insert(prefix);
27        }
28      }
29    }
30    return ans;
31  }
32};

Java Solution

1
2java
3import java.util.Set;
4import java.util.TreeSet;
5
6class Solution {
7    public int maxSumSubmatrix(int[][] matrix, int k) {
8        int rows = matrix.length;
9        int cols = matrix[0].length;
10        int maxSum = Integer.MIN_VALUE;
11        for(int leftCol = 0; leftCol < cols; leftCol++){
12            int[] sumRows = new int[rows];
13            for(int rightCol = leftCol; rightCol < cols; rightCol++){
14                for(int i = 0; i < rows; i++){
15                    sumRows[i] += matrix[i][rightCol];
16                }
17                TreeSet<Integer> set = new TreeSet<>();
18                set.add(0);
19                int currSum = 0;
20                for(int sumRow : sumRows){
21                    currSum += sumRow;
22                    Integer num = set.ceiling(currSum - k);
23                    if(num != null) maxSum = Math.max(maxSum, currSum - num);
24                    set.add(currSum);
25                }
26            }
27        }
28        return maxSum;
29    }
30}

Python Solution

1
2python
3import bisect
4
5class Solution:
6    def maxSumSubmatrix(self, matrix, k):
7        rows, cols = len(matrix), len(matrix[0])
8        maxSum = float('-inf')
9
10        for l in range(cols):
11            rowSums = [0] * rows
12            for r in range(l, cols):
13                for i in range(rows):
14                    rowSums[i] += matrix[i][r]
15                arr = [0]
16                cumSum = 0
17                for i in range(rows):
18                    cumSum += rowSums[i]
19                    loc = bisect.bisect_left(arr, cumSum - k)
20                    if loc < len(arr):
21                        maxSum = max(maxSum, cumSum - arr[loc])
22                    bisect.insort(arr, cumSum)
23        return maxSum

The complexity of this solution is O(rows^2*cols^2) which comes from the 4 nested loops. This complexity is manageable if number of columns is small. For larger number of columns, optimizing the solution would be necessary. The space complexity is O(rows) for storing the prefix sum in each row for current pair of columns.#### JavaScript Solution

While JavaScript does not have built-in binary search or Red-Black tree data structure like Python's bisect or Java's TreeSet, a third-party library like lodash or creating a utility function may be used for this purpose. The implementation remains conceptually same.

1
2javascript
3var Queue = require("collections/deque");
4function lower_bound(queue, target) {
5    let left = 0, right = queue.length - 1;
6    while (left < right) {
7        const mid = left + Math.floor((right - left) / 2);
8        if (queue[mid] < target)
9            left = mid + 1;
10        else
11            right = mid;
12    }
13    return left;
14}
15var maxSumSubmatrix = function(matrix, k) {
16    let row = matrix.length, col = matrix[0].length;
17    let dp = Array(row + 1).fill(0);
18    let result = -Infinity;
19    for (let l = 0; l < col; ++l) {
20        let sum = Array(row + 1).fill(0);
21        for (let r = l; r < col; ++r) {
22            for (let i = 1; i <= row; ++i) {
23                sum[i] = sum[i - 1] + matrix[i - 1][r];
24                dp[i] = sum[i];
25            }
26            dp.sort((a, b) => a - b);
27            let queue = new Queue();
28            for (let j = 1; j <= row; ++j) {
29                if(dp[j] <= k) result = Math.max(result, dp[j]);
30                if(dp[j] - dp[queue.peekFront()] > result && dp[j] - dp[queue.peekFront()] <= k)
31                    result = dp[j] - dp[queue.peekFront()];
32                while (queue.length !== 0 && dp[j] <= dp[queue.peekBack()])
33                    queue.popBack();
34                queue.pushBack(j);
35            }
36        }
37    }
38    return result;
39};

In this JavaScript solution, we use a Deque from the 'collections/deque' library to create a double-ended queue. After filling the dp array with prefix sums, we sort it to locate the subrectangle sum closest to K efficiently using binary search. Then, we use sorting and queue to find the maximum subrectangle sum that is not larger than K. The time complexity and space complexity remains the same as the previous solutions.