#363

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Max Sum of Rectangle No Larger Than K

Solve the "Max Sum of Rectangle No Larger Than K" problem using binary search over the valid sum space to optimize space and time complexity.

array binary search matrix prefix sum ordered set

Problem Statement

You are given an m x n matrix, along with an integer k. Your task is to find the maximum sum of any rectangle within the matrix such that the sum does not exceed k. It is guaranteed that a valid rectangle will exist with a sum no larger than k.

For instance, in a matrix with the values [[1, 0, 1], [0, -2, 3]] and k = 2, the rectangle with the sum of 2 is valid. You are required to implement an efficient solution that handles both space and time constraints effectively.

Examples

Example 1

Input: matrix = [[1,0,1],[0,-2,3]], k = 2

Output: 2

Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

Example 2

Input: matrix = [[2,2,-1]], k = 3

Output: 3

Example details omitted.

Constraints

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-100 <= matrix[i][j] <= 100
-105 <= k <= 105

Solution Approach

Binary Search on Sum Space

The core approach involves performing binary search over the possible sum values of the rectangle, adjusting the search space based on the sum constraints. This search helps narrow down the optimal sum that is less than or equal to k.

Prefix Sum Optimization

Prefix sum arrays are used to quickly calculate the sum of submatrices. This allows for efficient evaluation of different rectangle sums without recalculating values repeatedly.

Ordered Set for Efficient Sum Tracking

By maintaining an ordered set of possible sums for the rectangles, the solution efficiently tracks the largest possible valid sum no larger than k, reducing redundant computations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the binary search and matrix operations. In the worst case, the solution may involve iterating through rows and columns, leading to a time complexity of O(n^2 log k). Space complexity is influenced by the need to store prefix sums and ordered sets, resulting in O(n^2) space.

What Interviewers Usually Probe

Ability to efficiently handle a dynamic programming problem with constraints.
Skill in optimizing matrix-based solutions with space and time complexity considerations.
Proficiency in using binary search and ordered data structures for algorithmic optimization.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly implement the binary search to narrow down valid sums.
Neglecting to optimize sum calculations using prefix sums, leading to inefficient solutions.
Improper handling of edge cases, such as when k is very small or the matrix contains negative values.

Follow-up variants

Max Sum of Submatrix with Exact Sum: Instead of maximizing the sum, the goal is to find a submatrix with a sum equal to k.
Max Sum of Rectangle No Larger Than K with Multiple Queries: Handling multiple k values for the same matrix and optimizing for each query.
Max Sum of Subrectangle in a 2D Matrix with Larger k: An extension where k is larger, requiring different search space handling.

FAQ

What is the optimal approach for solving Max Sum of Rectangle No Larger Than K?

The optimal approach involves binary search on the sum space combined with prefix sum arrays and ordered sets to efficiently track the maximum valid rectangle sum.

How can I optimize the space complexity for this problem?

Using prefix sums and ordered sets helps in minimizing redundant space usage, allowing for efficient tracking of sums without recalculating them multiple times.

What is the time complexity of solving the Max Sum of Rectangle No Larger Than K problem?

The time complexity depends on the matrix size and the binary search, which typically leads to O(n^2 log k) complexity in the worst case.

What are common mistakes when solving this problem?

Common mistakes include failing to implement binary search correctly, neglecting to optimize with prefix sums, or improperly handling edge cases like negative values in the matrix.

How does binary search improve the solution to this problem?

Binary search helps by narrowing the possible sum space, reducing the number of potential rectangle sums that need to be checked, which optimizes performance.

terminal

Solution

Solution 1: Enumerate Boundaries + Ordered Set

We can enumerate the upper and lower boundaries $i$ and $j$ of the rectangle, then calculate the sum of the elements in each column within this boundary, and record it in the array $nums$. The problem is transformed into how to find the maximum subarray sum not exceeding $k$ in the array $nums$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        m, n = len(matrix), len(matrix[0])
        ans = -inf
        for i in range(m):
            nums = [0] * n
            for j in range(i, m):
                for h in range(n):
                    nums[h] += matrix[j][h]
                s = 0
                ts = SortedSet([0])
                for x in nums:
                    s += x
                    p = ts.bisect_left(s - k)
                    if p != len(ts):
                        ans = max(ans, s - ts[p])
                    ts.add(s)
        return ans

Continue Practicing

#497 random point in non overlapping rectangles #731 my calendar ii #1292 maximum side length of a square with sum less than or equal to threshold