Learning On the Way

363. Max Sum of Rectangle No Larger Than K

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.

class Solution { 
public: 
    int result = INT_MIN; 
    void updateResult(vector<int>& nums, int k) { 
        int sum = 0; 
        // Container to store sorted prefix sums. 
        set<int> sortedSum; 
        set<int>::iterator it; 
        // Add 0 as the prefix sum for an empty sub-array. 
        sortedSum.insert(0); 
        for (int& num : nums) { 
            // Running Sum. 
            sum += num; 
            // Get X where Running sum - X <= k such that sum - X is closest to k. 
            it = sortedSum.lower_bound(sum - k); 
            // If such X is found in the prefix sums. 
            // Get the sum of that sub array and update the global maximum resul. 
            if (it != sortedSum.end()) 
                result = max(result, sum - *it); 
            // Insert the current running sum to the prefix sums container. 
            sortedSum.insert(sum); 
        } 
    } 
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) { 
        // Stores the 1D representation of the matrix. 
        vector<int> rowSum(matrix[0].size()); 
        for (int i = 0; i < matrix.size(); i++) { 
            // Initialize the 1D representation with 0s. 
            fill(rowSum.begin(), rowSum.end(), 0); 
            // We convert the matrix between rows i..row inclusive to 1D array 
            for (int row = i; row < matrix.size(); row++) { 
                // Add the current row to the previous row. 
                // This converts the matrix between i..row to 1D array 
                for (int col = 0; col < matrix[0].size(); col++) 
                    rowSum[col] += matrix[row][col]; 
                // Run the 1D algorithm for `rowSum` 
                updateResult(rowSum, k); 
                // If result is k, this is the best possible answer, so return. 
                if (result == k) 
                    return result; 
            } 
        } 
        return result; 
    } 
};

class Solution: 
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int: 
        res = -float('inf') 
         
        def update(arr): 
            nonlocal res 
            from bisect import bisect_left, bisect_right, insort 
            prefix_sum = [0] 
            sum_ = 0 
            for v in arr: 
                sum_ += v 
                idx = bisect_left(prefix_sum, sum_ - k) 
                 
                if idx < len(prefix_sum): 
                    res = max(res, sum_ - prefix_sum[idx]) 
                 
                insort(prefix_sum, sum_) 
                             
        m, n = len(matrix), len(matrix[0]) 
         
        for i in range(m): 
            rowsum = [0] * n 
             
            for i2 in range(i, m): 
                for j in range(n): 
                    rowsum[j] += matrix[i2][j] 
                update(rowsum) 
                 
                if res == k: 
                    return k 
                     
        return res