Max Sum Of Rectangle No Larger Than K - Leetcode Solution

Problem:

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

Solution:

Let's first discuss how we can find the max sum of a rectangle in a 1D array such that its sum is no larger than k. We can use the same approach for a 2D matrix by considering all possible pairs of rows and applying the 1D solution to each pair of rows.

For example, consider the array [3, 2, 1, 2] and k = 4. We can find the max sum of a subarray such that its sum is no larger than k as follows:

• Initialize the max sum as 0 and prefix sum as 0.
• For each element x in the array, update the prefix sum as prefix_sum += x.
• If prefix_sum - k is present in the prefix sum dictionary, it means that the sum of a subarray from index i to j (where i <= j and j is the current index) is equal to prefix_sum - (prefix_sum - k) = k, which is the target sum. Update the max sum as max(max_sum, prefix_sum - (prefix_sum - k)).
• If prefix_sum is less than or equal to k, update the max sum as max(max_sum, prefix_sum).
• Finally, add the prefix sum to the prefix sum dictionary.

Let's now see how we can apply the above approach to a 2D matrix.

• Initialize the max sum as negative infinity.
• For each pair of rows i and j (where i <= j), create a 1D array A by taking the cumulative sum of the elements in each column from row i to row j.
• Apply the 1D solution to array A with target sum k. Let the result be res.
• If res is greater than the current max sum, update the max sum as res.
• Return the max sum.

Let's take an example to understand the above approach.

Consider the matrix

[ [1, 0, 1], [0, -2, 3] ]

and k = 2.

For i = 0 and j = 0, A = [1, 0, 1], which gives the max sum of a subarray such that its sum is no larger than k as 1.

For i = 0 and j = 1, A = [1, -2, 4], which gives the max sum of a subarray such that its sum is no larger than k as 1.

For i = 1 and j = 1, A = [0, -2, 3], which gives the max sum of a subarray such that its sum is no larger than k as 1.

The max sum among all possible pairs of rows is 1. Therefore, the function should return 1.

The time complexity of the above solution is O(n^3 log n), where n is the number of rows in the matrix. The space complexity is O(n^2). We can improve the time complexity by using a binary search based solution.

The key idea is that if we fix the left and right boundaries of the rectangle, we can apply the 1D solution to find the max sum of a subarray such that its sum is no larger than k. Therefore, we can use a sliding window technique to fix the left and right boundaries and make use of the 1D solution.

The implementation of the binary search based solution is provided below:

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        m, n = len(matrix), len(matrix[0])
        max_sum = float('-inf')
        
        for left in range(n):
            row_sums = [0] * m
                
            for right in range(left, n):
                for i in range(m):
                    row_sums[i] += matrix[i][right]
                
                prefix_sum_set = [0]
                prefix_sum = 0
                for row_sum in row_sums:
                    prefix_sum += row_sum
                    idx = bisect_left(prefix_sum_set, prefix_sum - k)
                    if idx < len(prefix_sum_set):
                        max_sum = max(max_sum, prefix_sum - prefix_sum_set[idx])
                    bisect.insort(prefix_sum_set, prefix_sum)
        
        return max_sum

The main loop of the function fixes the left and right boundaries of the rectangle. The inner loop updates the row sums for the current rectangle. The prefix sum set stores the prefix sums encountered so far. The bisect_left function returns the index of the first element in the set that is greater than or equal to prefix_sum - k. The max sum is updated if prefix_sum - prefix_sum_set[idx] is greater than the current max sum. Finally, the prefix sum is added to the prefix sum set.

The time complexity of the above solution is O(n^2 m log m), where n and m are the number of columns and rows in the matrix, respectively. The space complexity is O(m).

Overall, we have discussed two solutions to the Max Sum of Rectangle No Larger Than K problem on LeetCode. The first solution is the straightforward approach of considering all possible pairs of rows and applying the 1D solution to each pair. The second solution is a binary search based approach that makes use of the sliding window technique to find the max sum of a rectangle. The second approach is more efficient and has a lower time complexity.

1