363. Max Sum of Rectangle No Larger Than K

Problem

Given a 2-d array, with integer values (positive and negative). Given an integer k. Find the maximum sub-matrix sum <= k.

Solution

We can use dynamic programming to calculate the sums of the sub-matrices. Then by enumerating all the sub-matrices, we can get the answer. Complexity O(n^2m^2). An improve would be only enumerate the top, bottom and right border of the sub-matrix. Since we want For the left border we just select the left that maximize sum[right] - sum[left] subject to <= k, where sum is the sum of the sub-matrix with left=0 to right=index and the current top and bottom border. To maximize it, we can use binary search tree. It is equivalent to maximizing sum[left] subject to >= sum[right] - k. We insert the sum values into the tree, every time we query it the lower_bound of sum[right] - k, as we iterate all the right. The complexity is O(n^2mlogm).

Note: Python doesn't have a built-in binary search tree. We need to write our own.

Code

class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.val = value

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def lower_bound(self, value):
        node = self.root
        ret = None
        while node is not None:
            if value < node.val:
                ret = node.val
                node = node.left
            elif value == node.val:
                ret = node.val
                return ret
            else:
                node = node.right
        return ret

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
            return
        last_node = None
        node = self.root
        while node is not None:
            last_node = node
            if value < node.val:
                node = node.left
            else:
                node = node.right
        if value < last_node.val:
            last_node.left = Node(value)
        else:
            last_node.right = Node(value)

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        if len(matrix) > len(matrix[0]):
            new_matrix = []
            for i in range(len(matrix[0])):
                new_matrix.append([])
                for j in range(len(matrix)):
                    new_matrix[i].append(matrix[j][i])
            matrix = new_matrix
        num_rows = len(matrix)
        num_cols = len(matrix[0])
        sum_matrix = [[0 for j in range(num_cols + 1)] for i in range(num_rows + 1)]
        for i in range(num_rows):
            for j in range(num_cols):
                sum_matrix[i + 1][j + 1] = matrix[i][j] + sum_matrix[i + 1][j] + sum_matrix[i][j + 1] - sum_matrix[i][j]

        ret = - int(1 << 30)
        for height in range(1, num_rows + 1):
            for top in range(1, num_rows - height + 1 + 1):
                bottom = top + height - 1
                bst = BinarySearchTree()
                bst.insert(0)
                for right in range(1, num_cols + 1):
                    current_sum = sum_matrix[bottom][right] - sum_matrix[top - 1][right]
                    left_sum = bst.lower_bound(current_sum - k)
                    # print(right, current_sum, left_sum)
                    if left_sum is not None:
                        ret = max(ret, current_sum - left_sum)
                    bst.insert(current_sum)
        return ret