Maximum sum rectangle in a 2D matrix
Problem Statement
Given a 2D matrix of integers (can be positive and negative), find the rectangle (sub-matrix) with the maximum sum. Return the maximum sum.
Example:
- Input:
1, 2, -1, -4, -20
-8, -3, 4, 2, 1
3, 8, 10, 1, 3
-4, -1, 1, 7, -6
- Output:
29 - Explanation: The sub-matrix from rows 1-3 and columns 1-3 has sum = (-3+4+2) + (8+10+1) + (-1+1+7) = 29.
Noob-Friendly Explanation
Imagine a spreadsheet with numbers — some positive, some negative. You want to draw a rectangle around some cells such that when you add up all the numbers inside, you get the biggest possible total.
It's like choosing the best piece of land in a field where some areas are fertile (positive) and some are swampy (negative). You want the rectangle that gives you the most fertile area overall.
Approach 1: Brute Force
Intuition
Try every possible rectangle by fixing all four boundaries. Compute the sum and track the maximum.
Algorithm
- Fix top row, bottom row, left column, right column.
- Compute the sum of elements in this rectangle.
- Track the maximum sum.
class Solution {
public int maxSumRectangle(int[][] matrix) {
int rows = matrix.length, cols = matrix[0].length;
int maxSum = Integer.MIN_VALUE;
for (int top = 0; top < rows; top++) {
for (int bottom = top; bottom < rows; bottom++) {
for (int left = 0; left < cols; left++) {
for (int right = left; right < cols; right++) {
int sum = 0;
for (int i = top; i <= bottom; i++) {
for (int j = left; j <= right; j++) {
sum += matrix[i][j];
}
}
maxSum = Math.max(maxSum, sum);
}
}
}
}
return maxSum;
}
}Complexity Analysis
- Time Complexity: O(n^4 * m^2) - Six nested loops (four for boundaries, two for sum).
- Space Complexity: O(1) - Only a few variables.
Approach 2: Optimal (Kadane's on Column Compression)
Intuition
Fix the left and right columns. Compress each row into a single value (sum of that row between left and right columns). Now apply Kadane's algorithm on this 1D array to find the maximum subarray sum, which corresponds to the best top and bottom rows.
Algorithm
- Fix left column
land right columnr. - Compute
rowSum[i]= sum ofmatrix[i][l..r]for each row i. - Apply Kadane's algorithm on
rowSum[]to find max subarray sum. - Track the overall maximum.
class Solution {
public int maxSumRectangle(int[][] matrix) {
int rows = matrix.length, cols = matrix[0].length;
int maxSum = Integer.MIN_VALUE;
for (int left = 0; left < cols; left++) {
int[] rowSum = new int[rows];
for (int right = left; right < cols; right++) {
// Add current column to rowSum
for (int i = 0; i < rows; i++) {
rowSum[i] += matrix[i][right];
}
// Apply Kadane's algorithm on rowSum
int kadaneMax = kadane(rowSum);
maxSum = Math.max(maxSum, kadaneMax);
}
}
return maxSum;
}
private int kadane(int[] arr) {
int maxEndingHere = arr[0];
int maxSoFar = arr[0];
for (int i = 1; i < arr.length; i++) {
maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
}Complexity Analysis
- Time Complexity: O(n * m^2) - Two loops for column pairs (m^2) and Kadane's in O(n) for each.
- Space Complexity: O(n) - For the rowSum array.