Last updated on July 21st, 2024 at 04:33 am

Here, We see Max Sum of Rectangle No Larger Than K LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

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

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:

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

1. Max Sum of Rectangle No Larger Than K LeetCode Solution 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;        
    }
};

2. Max Sum of Rectangle No Larger Than K LeetCode Solution 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. Max Sum of Rectangle No Larger Than K LeetCode Solution 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;
};

4. Max Sum of Rectangle No Larger Than K Solution 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