Max Sum of Rectangle No Larger Than K

Max Sum of Rectangle No Larger Than K

What is this problem about?

The Max Sum of Rectangle No Larger Than K problem asks you to find the maximum sum of a rectangular subgrid within a 2D matrix, such that this sum is strictly less than or equal to a given integer k. The matrix contains integers that can be both positive and negative.

Why is this asked in interviews?

This is a notorious Hard-level matrix problem. It is a fusion of two famous algorithms: Kadane’s Algorithm (1D maximum subarray) and 1D Prefix Sum with Binary Search. Interviewers ask it to test if a candidate can "flatten" a 2D matrix problem into a 1D array problem, and then apply advanced tree-based search structures (like TreeSet in Java) to find an optimal bounded sum.

Algorithmic pattern used

This problem leverages 2D to 1D Flattening and Prefix Sums with Ordered Sets.

1. Choose a left column boundary and a right column boundary. This forms a vertical "band".
2. Flatten this band by summing the elements across each row into a 1D array.
3. Now, find the max subarray sum in this 1D array that is $\le k$. We do this by calculating a running prefix sum and storing previous prefix sums in an Ordered Set (Binary Search Tree).
4. For the current prefix sum P, we want a previous prefix sum P_prev such that P - P_prev <= k. Rearranging this, we need P_prev >= P - k. We can use the Ordered Set's ceiling() method to find the smallest P_prev that satisfies this in $O(\log N)$ time.

Example explanation

Matrix:

 1  0  1
 0 -2  3

Let k = 2. Assume we are evaluating the band from column 0 to column 2 (the whole matrix). Flattening rows into 1D:

• Row 0 sum: $1 + 0 + 1 = 2$
• Row 1 sum: $0 - 2 + 3 = 1$ 1D Array: [2, 1]. Iterate 1D array with Ordered Set:
• Init Set: {0}. Running sum = 0.
• num = 2: Running sum = 2. We need ceiling(2 - 2) -> ceiling(0). The set has 0. We found a valid sum: $2 - 0 = 2$. Max is 2. Add 2 to set: {0, 2}.
• num = 1: Running sum = 3. We need ceiling(3 - 2) -> ceiling(1). The set has 2. Valid sum: $3 - 2 = 1$. Max remains 2. Add 3 to set: {0, 2, 3}. The maximum valid sum is 2.

Common mistakes candidates make

A major mistake is trying to generate 2D Prefix Sums and using 4 nested loops to check every possible rectangle. This takes $O((M \times N)^2)$ time, which will Time Limit Exceed on large grids. Another common error is using Kadane's Algorithm on the 1D flattened array. Kadane's cannot handle the "$\le k$" constraint properly because negative numbers disrupt the sliding window boundaries; an Ordered Set is strictly required.

Interview preparation tip

When tackling the Max Sum of Rectangle No Larger Than K interview pattern, memorize the 1D sub-problem: "Find max subarray sum $\le k$". The 3-line code uses an Ordered Set: Integer target = set.ceiling(current_sum - k); if (target != null) max = Math.max(max, current_sum - target); set.add(current_sum); Once you can write this 1D logic flawlessly, flattening the 2D matrix into a 1D array is just a standard double-for-loop setup.