Max Sum of Rectangle No Larger Than K

We need to find the maximum sum of a rectangular submatrix in the given matrix such that the sum does not exceed the integer k.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from typing import List
import bisect

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        rows, cols = len(matrix), len(matrix[0])
        maxSum = float('-inf')

        # Loop through all combinations of left and right columns
        for left in range(cols):
            prefixSums = [0] * rows
            for right in range(left, cols):
                # Calculate prefix sums for rows
                for row in range(rows):
                    prefixSums[row] += matrix[row][right]
                    
                # Find the sum of rectangle that is less than or equal to k
                sortedSums = [0]
                currentSum = 0
                for prefixSum in prefixSums:
                    currentSum += prefixSum
                    index = bisect.bisect_left(sortedSums, currentSum - k)
                    if index < len(sortedSums):
                        maxSum = max(maxSum, currentSum - sortedSums[index])
                    bisect.insort(sortedSums, currentSum)

        return maxSum

The function loops through all combinations of left and right columns and calculates the prefix sums for the rows. It then uses binary search (with the help of the bisect module) to find the largest sum of a rectangle that is less than or equal to k, updating the maxSum accordingly. The final result is returned as the maximum sum that meets the conditions.

10 Prerequisite LeetCode Problems

“Max Sum of Rectangle No Larger Than K” involves dynamic programming and binary search in a 2D context. Here are some simpler problems to prepare for it:

53. Maximum Subarray: A basic dynamic programming problem, which introduces the idea of maintaining a running sum.
152. Maximum Product Subarray: A variation on the maximum subarray problem, which requires keeping track of both a maximum and a minimum value.
70. Climbing Stairs: A foundational dynamic programming problem that helps understand the base concept.
300. Longest Increasing Subsequence: This problem introduces binary search in the context of dynamic programming.
209. Minimum Size Subarray Sum: This problem requires finding a subarray with a sum above a certain value, and introduces the two-pointer technique.
325. Maximum Size Subarray Sum Equals k: This problem requires maintaining a sum and a hashmap, and introduces the idea of updating the answer based on a condition.
221. Maximal Square: This problem involves dynamic programming in a 2D context, which is directly relevant to the problem.
304. Range Sum Query 2D - Immutable: A problem that requires precomputing a 2D prefix sum, a concept which is used in the problem.
238. Product of Array Except Self: This problem requires keeping a running product, and introduces the idea of updating the result based on previously computed values.
240. Search a 2D Matrix II: This problem introduces the concept of binary search in a 2D matrix, which is a necessary skill to have when tackling this problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        ans = float("-inf")
        m, n = len(matrix), len(matrix[0])
        for i in range(n):
            lstSum = [0] * m
            for j in range(i, n):
                currSum = 0
                curlstSum = [0]
                for t in range(m):
                    lstSum[t] += matrix[t][j]
                    currSum += lstSum[t]
                    pos = bisect_left(curlstSum, currSum - k)
                    if pos < len(curlstSum):
                        if curlstSum[pos] == currSum - k:
                            return k
                        else:
                            ans = max(ans, currSum - curlstSum[pos])
                    insort(curlstSum, currSum)
        return ans

This problem involves finding the maximum sum of a rectangle in a 2D matrix that is no larger than k. This is a Limited Sum Maximization Problem.

Language Agnostic Coding Drills

Let’s break this problem down:

Understanding 2D Arrays and their Iteration: The problem operates on a 2D matrix, so the first skill to understand is how to iterate through a 2D array.
Accumulation and Tracking of Sums in an Array: In this problem, we maintain a running sum of values in the matrix and we track these sums in another list.
Introduction to Binary Search: We will be using binary search to find the position of certain elements in our list of sums. Understanding binary search is key to this problem.
Understanding the bisect_left Function: The bisect_left function is used to find the position at which an element should be inserted in the list to maintain sorted order.
Inserting Elements While Maintaining Sorted Order: The built-in function ‘insort’ from the ‘bisect’ module helps us to insert elements in the list while keeping the list sorted.
The Subarray Sum Problem and Its Variants: The core problem here is finding a subarray (in this case, a rectangular subarray within the matrix) with the largest sum. This is a common problem and there are various techniques to solve it, the most famous of which is Kadane’s algorithm. However, here we have an additional constraint: the sum cannot exceed ‘k’. This introduces an additional layer of complexity.
Application of the Above Concepts to the ‘Max Sum of Rectangle No Larger Than K’ Problem: Here, we need to apply all the above skills together. We iterate through the matrix, accumulating sums, and tracking the maximum sum we’ve seen that doesn’t exceed ‘k’. We use binary search to efficiently find if we can get a sum closer to ‘k’ with our current sum.

Here’s how we might apply these steps to solve the problem:

Iterate over all possible pairs of columns in the matrix.
For each pair of columns, calculate a list of row sums for rows between those two columns.
Then, for each new sum, we can use binary search to find if we have a previous accumulated sum which will allow us to get closer to ‘k’.
If we can get exactly ‘k’, we can return it. This is the best possible answer.
Otherwise, we keep track of the closest sum to ‘k’ that we’ve seen so far. This will be our answer.

The use of binary search to find sums closest to ‘k’ is the key to making this algorithm efficient. Without it, we would have to check all possible pairs of sums, which would take too long.

Targeted Drills in Python

Here’s how we can break the code into smaller units and write a coding drill for each concept.

Understanding 2D Arrays and their Iteration:

Creating and Iterating over 2D arrays

1
2
3
4
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for row in matrix:
    for elem in row:
        print(elem)

Accumulation and Tracking of Sums in an Array:

Creating a list to keep track of running sums

1
2
3
4
5
6
7
array = [1, 2, 3, 4, 5]
running_sum = 0
sum_list = []
for num in array:
    running_sum += num
    sum_list.append(running_sum)
print(sum_list)

Introduction to Binary Search:

Implementing binary search algorithm

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def binary_search(array, target):
    left, right = 0, len(array) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Understanding the bisect_left Function:
Using bisect_left to find the insertion point to maintain sorted list
1 2 3
import bisect array = [1, 3, 4, 4, 6, 8] print(bisect.bisect_left(array, 4))

Inserting Elements While Maintaining Sorted Order:

Using insort to insert an element into sorted list

1
2
3
4
import bisect
array = [1, 3, 4, 4, 6, 8]
bisect.insort(array, 5)
print(array)

The Subarray Sum Problem and Its Variants:

Implementing Kadane’s algorithm to find maximum subarray sum

1
2
3
4
5
6
def max_subarray_sum(array):
    max_sum = current_sum = array[0]
    for num in array[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

Application of the Above Concepts to the ‘Max Sum of Rectangle No Larger Than K’ Problem:
After understanding and practicing the above drills, you can try to solve similar problems before tackling the final problem. Start with problems related to subarray sums and binary search. Once you’re comfortable with these concepts, proceed to solve the final problem.