Max Sum of Rectangle No Larger Than K LeetCode Solution

Last updated on January 21st, 2025 at 02:21 am

Here, we see a Max Sum of Rectangle No Larger Than K LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Binary Search, Dynamic Programming, Queue

Companies

Google

Level of Question

Hard

Max Sum of Rectangle No Larger Than K LeetCode Solution

Max Sum of Rectangle No Larger Than K LeetCode Solution

1. Problem Statement

Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.

It is guaranteed that there will be a rectangle with a sum no larger than k.

Example 1:

sum grid

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

Example 2:
Input: matrix = [[2,2,-1]], k = 3
Output: 3

2. Coding Pattern Used in Solution

The coding pattern used in this problem is “2D Prefix Sum with Binary Search”. The algorithm uses a combination of prefix sums (to calculate cumulative sums efficiently) and binary search (to find the maximum submatrix sum that does not exceed k).

3. Code Implementation in Different Languages

3.1 Max Sum of Rectangle No Larger Than K C++

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
    if (matrix.empty()) return 0;
    int row = matrix.size(), col = matrix[0].size(), res = INT_MIN;
    for (int l = 0; l < col; ++l) {
        vector<int> sums(row, 0);
        for (int r = l; r < col; ++r) {
            for (int i = 0; i < row; ++i) {
                sums[i] += matrix[i][r];
            }
            set<int> accuSet;
            accuSet.insert(0);
            int curSum = 0, curMax = INT_MIN;
            for (int sum : sums) {
                curSum += sum;
                set<int>::iterator it = accuSet.lower_bound(curSum - k);
                if (it != accuSet.end()) curMax = std::max(curMax, curSum - *it);
                accuSet.insert(curSum);
            }
            res = std::max(res, curMax);
        }
    }
    return res;        
    }
};

3.2 Max Sum of Rectangle No Larger Than K Java

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int result = Integer.MIN_VALUE;
        for(int left =0 ;left<matrix[0].length; left++){   
            int[] rSum = new int[matrix.length];
            for(int right = left;right<matrix[0].length;right++){
                for(int row=0; row < matrix.length; row++)
                    rSum[row] += matrix[row][right];
                TreeSet<Integer> set = new TreeSet<>();
                set.add(0);
                int cs = 0;
                for(int a: rSum){
                    cs += a;
                    Integer target = set.ceiling(cs-k);
                    if(target !=null)
                        result = Math.max(result,cs-target);
                    set.add(cs);
                }
            }
        }
        return result;
    }
}

3.3 Max Sum of Rectangle No Larger Than K JavaScript

var maxSumSubmatrix = function(grid, k) {
    let c = grid[0].length
    let r = grid.length
    let i, j
    let dp = [...Array(r + 1)].map(e => Array(c).fill(0))
    i = -1;
    while (++i < r) {
        j = -1;
        while (++j < c)
            dp[i + 1][j] = dp[i][j] + grid[i][j];
    }
    let res = -2147483648;
    i = -1;
    while (++i < r) {
        let ii = i;
        while (++ii < r + 1) {
            j = -1;
            while (++j < c) {
                let tmp = 0;
                let jj = j - 1;
                while (++jj < c) {
                    tmp += dp[ii][jj] - dp[i][jj];
                    if (tmp == k)
                        return k;
                    if (tmp < k && res < tmp)
                        res = tmp;
                }
            }
        }
    }
    return res;
};

3.4 Max Sum of Rectangle No Larger Than K Python

class Solution(object):
    def maxSumSubmatrix(self, matrix, k):
        m, n = len(matrix), len(matrix[0])
        max_sum = -float('inf')
        for left in range(n):
            temp = [0] * m
            for right in range(left, n):
                for i in range(m):
                    temp[i] += matrix[i][right]
                cum_sum = 0
                cum_sum_set = sorted([0])
                for t in temp:
                    cum_sum += t
                    it = bisect_left(cum_sum_set, cum_sum - k)
                    if it != len(cum_sum_set):
                        max_sum = max(max_sum, cum_sum - cum_sum_set[it])
                    bisect.insort(cum_sum_set, cum_sum)
        return max_sum

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n2 * m * log m)O(m)
JavaO(n2 * m * log m)O(m)
JavaScriptO(m2 * n2)O(m * n)
PythonO(n2 * m * log m)O(m)
  • C++ and Java: Both use efficient binary search with a set/TreeSet, leading to (O(\log m)) complexity for each row.
  • Python: Uses bisect for binary search, achieving similar efficiency as C++/Java.
  • JavaScript: Lacks binary search optimization, resulting in a less efficient (O(m^2 \cdot n^2)) time complexity.
  • Space Complexity: All implementations (except JavaScript) use (O(m)) space for intermediate calculations. JavaScript uses (O(m \cdot n)) due to the dp array.
Scroll to Top