363. Max Sum of Rectangle No Larger Than K

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        """ tc O(C*C*R*lgR)  => O(max(R,C)^2 * min(R,C) * lg(min(R,C))) sc O(R)  
        *** here assume rows >> cols 
        1. create an array to save prefix sum for each row  
        2. for psum[0] ... psum[right-1], find an idx  s.t. psum[idx] >= psum[right] - k 
        3. compare with global maxv, find the max value that <= k 
        """
        rows, cols = len(matrix), len(matrix[0])
        res = float('-inf')
        
        for i in range(rows):
            for j in range(cols-1):
                matrix[i][j+1] += matrix[i][j] 
        
        for left in range(cols):
            for right in range(left,cols):
                # for one row, presum [left,right] array
                arr = [matrix[row][right] - (matrix[row][left-1] if left > 0 else 0 ) for row in range(rows)]
                res = max(res, self.maxSubarraySum(arr,k))
        return res 
    
    def maxSubarraySum(self, A, k):
        maxv = float('-inf')
        psum = 0
        sortedL = [0]
        for a in A:
            psum += a # psum_right
            idx = bisect.bisect_left(sortedL, psum-k) #psum_right - psum_left <= k  psum_right - k <= psum_left
            if idx < len(sortedL):
                maxv = max(maxv, psum - sortedL[idx]) #psum_right - psum_left 
            bisect.insort(sortedL, psum) # can use OrderedList to reduce time complexity to O(LgR)
        return maxv