Leetcode Max Sum of Rectangle No Larger Than K problem solution

In this Leetcode Max Sum of Rectangle No Larger Than K problem solution you have 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.

Problem solution in Python.

import bisect

def csum_less_than_k(nums, k):
    ans = float('-inf')
    slist = [0]

    for x in range(1, len(nums)):
        nums[x] += nums[x-1]

    for p in nums:
        idx = bisect.bisect_left(slist, p-k)
        if idx < len(slist):
            ans = max(ans, p-slist[idx])

        bisect.insort(slist, p)

    return ans

class Solution:
    def maxSumSubmatrix(self, matrix, k: int) -> int:
        R = len(matrix)
        C = len(matrix[0])
        ans = float('-inf')
        for r in range(R):
            for c in range(1, C):
                matrix[r][c] += matrix[r][c-1]

        for left_edge in range(C):
            for right_edge in range(left_edge, C):
                ledge = lambda i: matrix[i][left_edge-1] if left_edge > 0 else 0
                one_d_array = [matrix[i][right_edge]-ledge(i) for i in range(R)]
                ans = max(ans, csum_less_than_k(one_d_array, k))

        return ans

Problem solution in Java.

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int[][] prefixSums = calculatePrefixSums(matrix);
        return maxSum(prefixSums, k);
    }
    
    private int maxSum(int[][] prefixSums, int k) {
        int n = prefixSums.length;
        int m = prefixSums[0].length;
        int answer = Integer.MIN_VALUE;
        
        for (int x = 1; x < m; x++) {
            for (int l = 0; l < x; l++) {
                TreeSet<Integer> set = new TreeSet<>();
                set.add(0);

                for (int y = 1; y < n; y++) {
                    int totalSum = prefixSums[y][x] - prefixSums[y][l];
                    Integer previous = set.ceiling(totalSum - k);

                    if (previous != null) {
                        answer = Math.max(answer, totalSum - previous);
                    }

                    set.add(totalSum);
                }
            }
        }
        
        return answer;
    }
    
    private int[][] calculatePrefixSums(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] prefixSums = new int[n + 1][m + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                prefixSums[i][j] = prefixSums[i][j-1] + prefixSums[i-1][j] + matrix[i-1][j-1] - prefixSums[i-1][j-1];
            }
        }
        
        return prefixSums;
    }
}

Problem solution in C++.

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int n = matrix.size() ;
        int m = matrix[0].size();
        int temp[n];
        memset(temp,0,sizeof temp);
        bool does = false;
        int maxx = INT_MAX;
        for(int i = 0 ; i < matrix.size() ; ++i){
            for(int j = 0 ; j < matrix[0].size() ; ++j){
                if(matrix[i][j] >= 0) does = true;
                maxx = max(maxx , matrix[i][j]);
            }
        }
        if(does == false){
            return maxx;
        }
        int maxsum = INT_MIN;
        for(int left = 0 ; left < m ; ++left){
            for(int right = left ; right < m ; ++right){
                if(left == right){
                    memset(temp , 0 , sizeof temp);
                }
                for(int i = 0 ; i < n ; ++i){
                    temp[i]+=matrix[i][right];
                }
                 
                int currsum = 0 ;
                set<int> s; 
                s.insert(0);
                for(int i = 0 ; i < n ; ++i){
                    currsum+=temp[i];
                    int req = currsum - k; 
                    auto it = s.lower_bound(req);
                    if(it != s.end()){
                        maxsum = max(maxsum , currsum - *it);
                    }
                    s.insert(currsum);
                }
            }
        }
        return maxsum;
    }
};