📘 Problem Statement
Given an m x n 2D matrix of integers and an integer k, return the maximum sum of a rectangle (submatrix) such that the sum is no larger than k.
🧠 Key Insight
- The naive brute-force approach would involve checking all submatrices — which is computationally too expensive.
- Instead, reduce the 2D problem to 1D by fixing the left and right column boundaries and computing row-wise prefix sums.
- Then for each reduced 1D array, find the maximum subarray sum that is no more than
k using prefix sums and binary search.
🐍 Python Code
python
import bisect
class Solution:
def maxSumSubmatrix(self, matrix, k):
if not matrix:
return 0
rows, cols = len(matrix), len(matrix[0])
max_sum = float('-inf')
for left in range(cols):
row_sums = [0] * rows
for right in range(left, cols):
for i in range(rows):
row_sums[i] += matrix[i][right]
prefix_sums = [0]
curr_sum = 0
curr_max = float('-inf')
for sum_val in row_sums:
curr_sum += sum_val
idx = bisect.bisect_left(prefix_sums, curr_sum - k)
if idx < len(prefix_sums):
curr_max = max(curr_max, curr_sum - prefix_sums[idx])
bisect.insort(prefix_sums, curr_sum)
max_sum = max(max_sum, curr_max)
return max_sum
🔍 Step-by-Step Explanation
1. Loop Over All Column Pairs
python
for left in range(cols):
for right in range(left, cols):
- We fix the left and right column boundaries to define the width of submatrices.
2. Build a Row Sum Array
python
for i in range(rows):
row_sums[i] += matrix[i][right]
- Collapse the 2D matrix into a 1D array by summing each row between the fixed columns.
3. Use Prefix Sums + Binary Search (Bisect)
python
idx = bisect.bisect_left(prefix_sums, curr_sum - k)
- We want to find if there's a previous prefix sum such that the current subarray sum
<= k.
- The idea is similar to Kadane’s algorithm but constrained by a cap (
k).
💡 Example
python
Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation:
- The rectangle [[0,1],[-2,3]] has a sum of 2 which is the best you can get ≤ k.
⏱️ Time & Space Complexity
MetricComplexityTime ComplexityO(n² × m log m)Space ComplexityO(m)
n = number of columns, m = number of rows.- We loop over all
n² column pairs and do m log m for each with prefix sums + binary search.
🧵 Final Thoughts
This problem is a textbook case of:
- Reducing dimensions: turning a 2D matrix into 1D problems.
- Using binary search with prefix sums to manage constraints efficiently.
Perfect for practicing advanced DP, matrix handling, and optimization strategies.