LeetCode 363 - Max Sum of Rectangle No Larger Than K
The problem asks us to find the rectangular submatrix whose sum is as large as possible while still being less than or equal to a given integer k. A rectangle in a matrix is any contiguous block of cells formed by choosing a range of rows and a range of columns.
Difficulty: 🔴 Hard
Topics: Array, Binary Search, Matrix, Prefix Sum, Ordered Set
Solution
Problem Understanding
The problem asks us to find the rectangular submatrix whose sum is as large as possible while still being less than or equal to a given integer k.
A rectangle in a matrix is any contiguous block of cells formed by choosing a range of rows and a range of columns. The rectangle can be as small as a single element or as large as the entire matrix.
We are given:
- A 2D integer matrix
matrix - An integer
k
We must return the maximum rectangle sum such that:
rectangle_sum <= k
Among all valid rectangles, we want the one with the largest possible sum.
For example, consider:
matrix = [
[1, 0, 1],
[0, -2, 3]
]
k = 2
One valid rectangle is:
[
[0, 1],
[-2, 3]
]
Its sum is:
0 + 1 - 2 + 3 = 2
Since 2 <= k and no larger valid rectangle sum exists, the answer is 2.
The constraints are important:
m, n <= 100- Values can be negative
kcan also be negative
A naive brute-force approach that checks every rectangle explicitly becomes extremely expensive because the number of possible rectangles grows rapidly with matrix size.
The presence of negative numbers is especially important. If all numbers were positive, we could use sliding window techniques. Negative values destroy monotonic behavior, so we need a more advanced approach.
The problem also guarantees that at least one rectangle sum will be less than or equal to k. That means we never need to handle a "no valid answer" scenario.
Several edge cases are important:
- A single-cell matrix
- All negative values
kbeing negative- The optimal rectangle being only one element
- The optimal rectangle spanning the entire matrix
- Cases where the exact value
kexists, which is the best possible answer
Approaches
Brute Force Approach
The most direct solution is to enumerate every possible rectangle in the matrix.
A rectangle is defined by:
- Top row
- Bottom row
- Left column
- Right column
That already gives four nested loops.
For each rectangle, we compute its sum and check whether:
sum <= k
If valid, we update the answer.
To speed up rectangle sum computation, we can precompute a 2D prefix sum array so each rectangle sum can be queried in constant time.
Even with prefix sums, the total number of rectangles is:
O(m² * n²)
Since each rectangle is checked individually, this becomes too slow for matrices up to 100 x 100.
Key Insight for the Optimal Solution
The critical observation is that we can reduce the 2D problem into a sequence of 1D problems.
Suppose we fix two column boundaries:
left and right
For every row, we compute the sum of elements between those columns.
This compresses the matrix into a 1D array where:
row_sums[i]
represents the sum of row i between columns left and right.
Now the problem becomes:
Find the maximum subarray sum no larger than
k.
This is a classic prefix sum + ordered set problem.
For a prefix sum array:
current_prefix
we want a previous prefix:
previous_prefix
such that:
current_prefix - previous_prefix <= k
Rearranging:
previous_prefix >= current_prefix - k
So for every current prefix sum, we search for the smallest previous prefix sum that is at least:
current_prefix - k
An ordered structure allows this query efficiently.
This transforms the problem from expensive rectangle enumeration into a much faster approach.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(m² * n²) | O(m * n) | Enumerates every rectangle explicitly |
| Optimal | O(min(m, n)² * max(m, n) * log(max(m, n))) | O(max(m, n)) | Compresses rows or columns into 1D subarray problems |
Algorithm Walkthrough
Optimal Algorithm
- Determine whether rows or columns are smaller.
Since the algorithm fixes pairs of boundaries, we want to minimize the squared dimension. If rows are larger than columns, we iterate over column pairs. Otherwise, we iterate over row pairs. 2. Fix the left boundary.
Start with a column index left.
3. Expand the right boundary.
For every right >= left, maintain a running array:
row_sums
where each entry stores the sum of elements between columns left and right for that row.
4. Convert the problem into a 1D maximum subarray sum problem.
We now need:
max subarray sum <= k
for the array row_sums.
5. Use prefix sums.
As we iterate through row_sums, maintain:
current_prefix
A subarray sum can be computed as:
current_prefix - previous_prefix
- Use an ordered set of previous prefix sums.
We need the largest valid subarray sum:
current_prefix - previous_prefix <= k
Rearanging gives:
previous_prefix >= current_prefix - k
So we search for the smallest prefix sum greater than or equal to:
current_prefix - k
- Use binary search.
Store prefix sums in sorted order. Python uses bisect_left on a sorted list.
8. Update the answer.
If a valid previous prefix exists, compute:
current_prefix - previous_prefix
and update the global maximum. 9. Insert the current prefix sum into the ordered structure.
This makes it available for future subarrays. 10. Repeat for all boundary pairs.
Every possible rectangle is considered through boundary compression.
Why it works
Fixing two column boundaries uniquely determines the horizontal extent of a rectangle. Compressing the rows converts each rectangle into a contiguous subarray problem.
The prefix sum identity guarantees that every subarray sum can be represented as:
current_prefix - previous_prefix
The ordered set ensures we efficiently find the best previous prefix that keeps the subarray sum within k. Since every possible boundary pair and every possible subarray are considered, the algorithm always finds the optimal rectangle.
Python Solution
from typing import List
from bisect import bisect_left, insort
class Solution:
def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
rows = len(matrix)
cols = len(matrix[0])
# Ensure we iterate over the smaller dimension squared
if rows > cols:
matrix = list(zip(*matrix))
rows, cols = cols, rows
best_sum = float("-inf")
for left in range(cols):
row_sums = [0] * rows
for right in range(left, cols):
for r in range(rows):
row_sums[r] += matrix[r][right]
prefix_sum = 0
sorted_prefix = [0]
current_best = float("-inf")
for value in row_sums:
prefix_sum += value
target = prefix_sum - k
index = bisect_left(sorted_prefix, target)
if index < len(sorted_prefix):
current_best = max(
current_best,
prefix_sum - sorted_prefix[index]
)
insort(sorted_prefix, prefix_sum)
best_sum = max(best_sum, current_best)
return best_sum
The implementation begins by determining whether the matrix should be transposed. This optimization matters because the algorithm performs quadratic work on one dimension. Squaring the smaller dimension reduces runtime significantly.
For each pair of column boundaries, we maintain row_sums, which stores the compressed row values between the current left and right columns.
The problem then becomes finding the maximum subarray sum no larger than k.
The prefix sum technique converts subarray sums into differences between prefix sums. The sorted prefix structure allows binary searching for the best candidate prefix efficiently.
bisect_left finds the smallest prefix sum greater than or equal to:
prefix_sum - k
This guarantees the resulting subarray sum does not exceed k.
Finally, every valid candidate updates the global answer.
Go Solution
package main
import (
"math"
"sort"
)
func maxSumSubmatrix(matrix [][]int, k int) int {
rows := len(matrix)
cols := len(matrix[0])
// Transpose if rows > cols
if rows > cols {
transposed := make([][]int, cols)
for c := 0; c < cols; c++ {
transposed[c] = make([]int, rows)
for r := 0; r < rows; r++ {
transposed[c][r] = matrix[r][c]
}
}
matrix = transposed
rows, cols = cols, rows
}
bestSum := math.MinInt32
for left := 0; left < cols; left++ {
rowSums := make([]int, rows)
for right := left; right < cols; right++ {
for r := 0; r < rows; r++ {
rowSums[r] += matrix[r][right]
}
prefixSum := 0
sortedPrefix := []int{0}
currentBest := math.MinInt32
for _, value := range rowSums {
prefixSum += value
target := prefixSum - k
index := sort.SearchInts(sortedPrefix, target)
if index < len(sortedPrefix) {
candidate := prefixSum - sortedPrefix[index]
if candidate > currentBest {
currentBest = candidate
}
}
insertIndex := sort.SearchInts(sortedPrefix, prefixSum)
sortedPrefix = append(sortedPrefix, 0)
copy(sortedPrefix[insertIndex+1:], sortedPrefix[insertIndex:])
sortedPrefix[insertIndex] = prefixSum
}
if currentBest > bestSum {
bestSum = currentBest
}
}
}
return bestSum
}
The Go version follows the same algorithmic structure as the Python solution.
Since Go does not provide a built-in balanced tree or ordered multiset in the standard library, we maintain a sorted slice manually.
sort.SearchInts performs binary search to locate insertion points and valid prefix candidates.
Insertion into the sorted slice requires shifting elements manually using copy.
Go integers are sufficient for this problem because the constraints keep sums safely within 32-bit integer range.
Worked Examples
Example 1
Input:
matrix = [
[1, 0, 1],
[0, -2, 3]
]
k = 2
We fix column boundaries.
Left = 0, Right = 0
Compressed rows:
[1, 0]
Now solve maximum subarray sum <= 2.
| Step | Value | Prefix Sum | Target | Sorted Prefix | Best |
|---|---|---|---|---|---|
| Start | - | 0 | - | [0] | -inf |
| 1 | 1 | 1 | -1 | [0] | 1 |
| 2 | 0 | 1 | -1 | [0,1] | 1 |
Current best:
1
Left = 0, Right = 1
Compressed rows:
[1, -2]
| Step | Value | Prefix Sum | Target | Sorted Prefix | Best |
|---|---|---|---|---|---|
| Start | - | 0 | - | [0] | -inf |
| 1 | 1 | 1 | -1 | [0] | 1 |
| 2 | -2 | -1 | -3 | [0,1] | 1 |
Best remains:
1
Left = 0, Right = 2
Compressed rows:
[2, 1]
| Step | Value | Prefix Sum | Target | Sorted Prefix | Best |
|---|---|---|---|---|---|
| Start | - | 0 | - | [0] | -inf |
| 1 | 2 | 2 | 0 | [0] | 2 |
| 2 | 1 | 3 | 1 | [0,2] | 2 |
We found exactly 2, which equals k.
Final answer:
2
Example 2
Input:
matrix = [[2,2,-1]]
k = 3
Possible subarrays:
| Rectangle | Sum |
|---|---|
| [2] | 2 |
| [2] | 2 |
| [-1] | -1 |
| [2,2] | 4 |
| [2,-1] | 1 |
| [2,2,-1] | 3 |
Maximum valid sum:
3
Output:
3
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(min(m, n)² * max(m, n) * log(max(m, n))) | We enumerate boundary pairs and solve a 1D ordered-prefix problem |
| Space | O(max(m, n)) | Prefix sums and compressed row storage |
The algorithm iterates over all pairs of boundaries in the smaller dimension. For each pair, it processes the larger dimension once while maintaining a sorted prefix structure with binary search operations.
The logarithmic factor comes from ordered prefix sum lookups and insertions.
Test Cases
from typing import List
class Solution:
def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
from bisect import bisect_left, insort
rows = len(matrix)
cols = len(matrix[0])
if rows > cols:
matrix = list(zip(*matrix))
rows, cols = cols, rows
best_sum = float("-inf")
for left in range(cols):
row_sums = [0] * rows
for right in range(left, cols):
for r in range(rows):
row_sums[r] += matrix[r][right]
prefix_sum = 0
sorted_prefix = [0]
for value in row_sums:
prefix_sum += value
index = bisect_left(sorted_prefix, prefix_sum - k)
if index < len(sorted_prefix):
best_sum = max(
best_sum,
prefix_sum - sorted_prefix[index]
)
insort(sorted_prefix, prefix_sum)
return best_sum
sol = Solution()
assert sol.maxSumSubmatrix([[1,0,1],[0,-2,3]], 2) == 2 # Provided example
assert sol.maxSumSubmatrix([[2,2,-1]], 3) == 3 # Single row example
assert sol.maxSumSubmatrix([[5]], 5) == 5 # Single element exact match
assert sol.maxSumSubmatrix([[-5]], -2) == -5 # Negative single element
assert sol.maxSumSubmatrix([[2,-1,2]], 3) == 3 # Entire row valid
assert sol.maxSumSubmatrix([[2,-1,2]], 2) == 2 # Must avoid exceeding k
assert sol.maxSumSubmatrix([[1,1],[1,1]], 3) == 3 # Rectangle smaller than full matrix
assert sol.maxSumSubmatrix([[-1,-2],[-3,-4]], -1) == -1 # All negative values
assert sol.maxSumSubmatrix([[100]], 50) == float("-inf") or True # Constraint guarantees valid answer
assert sol.maxSumSubmatrix([[0,0],[0,0]], 0) == 0 # All zeros
assert sol.maxSumSubmatrix([[3,-2,5],[-1,4,-3]], 6) == 6 # Mixed positive and negative
Test Summary
| Test | Why |
|---|---|
[[1,0,1],[0,-2,3]], k=2 |
Validates the core example |
[[2,2,-1]], k=3 |
Tests single-row handling |
[[5]], k=5 |
Single-cell exact match |
[[-5]], k=-2 |
Negative values with negative k |
[[2,-1,2]], k=3 |
Entire row is optimal |
[[2,-1,2]], k=2 |
Must reject larger invalid sum |
[[1,1],[1,1]], k=3 |
Best rectangle is not the whole matrix |
[[-1,-2],[-3,-4]], k=-1 |
All-negative matrix |
[[0,0],[0,0]], k=0 |
Zero-valued matrix |
[[3,-2,5],[-1,4,-3]], k=6 |
Mixed-value stress case |
Edge Cases
All Negative Numbers
A matrix containing only negative values can easily break algorithms that assume larger rectangles always produce larger sums.
For example:
[
[-3, -2],
[-5, -1]
]
with:
k = -2
The best answer is -2, not a larger rectangle.
The prefix sum approach handles this naturally because it evaluates every possible subarray sum regardless of sign.
Single Element Matrix
When the matrix contains only one cell, that cell itself is the only possible rectangle.
Example:
matrix = [[5]]
k = 5
The algorithm still works because the compressed array becomes length one, and the prefix logic correctly identifies the valid subarray.
Exact Match to k
If a rectangle sum equals k, that is automatically the optimal answer because no larger valid sum can exist.
Example:
matrix = [
[2, 1]
]
k = 3
The algorithm naturally detects this during prefix sum evaluation. No special handling is required.
Large Rectangles With Negative Values
Negative numbers can make larger rectangles unexpectedly optimal.
For example:
[
[5, -4],
[-3, 2]
]
A naive greedy strategy might fail because adding cells can decrease the sum.
The prefix sum formulation guarantees all possible contiguous ranges are evaluated correctly, including those where negative values improve feasibility under k.