Introduction
Given an m x n matrix of integers, find the rectangle whose border elements have the maximum sum. The border consists of the top row, bottom row, left column, and right column of the rectangle. The brute-force approach checks all O(m^2 * n^2) possible rectangles and computes each border sum. Using prefix sums for rows and columns, each border sum can be computed in O(1), bringing the total complexity to O(m^2 * n^2) time with O(m * n) space for the prefix arrays.
Problem Definition
For a matrix:
1 2 3 4
5 6 7 8
9 10 11 12
The rectangle from (0,0) to (2,3) has border: 1+2+3+4 + 8+12 + 11+10+9 + 5 = 65. The interior elements (6, 7) are not counted.
Brute-Force Approach
Enumerate all rectangles defined by (top, left, bottom, right) and compute the border sum:
1#include <iostream>
2#include <vector>
3#include <climits>
4
5using namespace std;
6
7int borderSum(const vector<vector<int>>& mat, int r1, int c1, int r2, int c2) {
8 int sum = 0;
9
10 // Top row
11 for (int c = c1; c <= c2; c++)
12 sum += mat[r1][c];
13
14 // Bottom row (if different from top)
15 if (r2 != r1)
16 for (int c = c1; c <= c2; c++)
17 sum += mat[r2][c];
18
19 // Left column (excluding corners already counted)
20 for (int r = r1 + 1; r < r2; r++)
21 sum += mat[r][c1];
22
23 // Right column (excluding corners, if different from left)
24 if (c2 != c1)
25 for (int r = r1 + 1; r < r2; r++)
26 sum += mat[r][c2];
27
28 return sum;
29}
30
31int main() {
32 vector<vector<int>> mat = {
33 {1, 2, 3, 4},
34 {5, 6, 7, 8},
35 {9, 10, 11, 12}
36 };
37
38 int m = mat.size(), n = mat[0].size();
39 int maxSum = INT_MIN;
40 int bestR1, bestC1, bestR2, bestC2;
41
42 for (int r1 = 0; r1 < m; r1++)
43 for (int c1 = 0; c1 < n; c1++)
44 for (int r2 = r1; r2 < m; r2++)
45 for (int c2 = c1; c2 < n; c2++) {
46 int s = borderSum(mat, r1, c1, r2, c2);
47 if (s > maxSum) {
48 maxSum = s;
49 bestR1 = r1; bestC1 = c1;
50 bestR2 = r2; bestC2 = c2;
51 }
52 }
53
54 cout << "Max border sum: " << maxSum << endl;
55 cout << "Rectangle: (" << bestR1 << "," << bestC1
56 << ") to (" << bestR2 << "," << bestC2 << ")" << endl;
57 return 0;
58}
This is O(m^2 * n^2 * (m + n)) — the inner border sum computation is O(m + n).
Optimized Approach with Prefix Sums
Precompute row and column prefix sums to calculate each border sum in O(1):
1#include <iostream>
2#include <vector>
3#include <climits>
4
5using namespace std;
6
7int main() {
8 vector<vector<int>> mat = {
9 {1, 2, 3, 4},
10 {5, 6, 7, 8},
11 {9, 10, 11, 12}
12 };
13
14 int m = mat.size(), n = mat[0].size();
15
16 // Row prefix sums: rowSum[r][c] = sum of mat[r][0..c-1]
17 vector<vector<int>> rowSum(m, vector<int>(n + 1, 0));
18 for (int r = 0; r < m; r++)
19 for (int c = 0; c < n; c++)
20 rowSum[r][c + 1] = rowSum[r][c] + mat[r][c];
21
22 // Column prefix sums: colSum[r][c] = sum of mat[0..r-1][c]
23 vector<vector<int>> colSum(m + 1, vector<int>(n, 0));
24 for (int c = 0; c < n; c++)
25 for (int r = 0; r < m; r++)
26 colSum[r + 1][c] = colSum[r][c] + mat[r][c];
27
28 auto rowRangeSum = [&](int r, int c1, int c2) {
29 return rowSum[r][c2 + 1] - rowSum[r][c1];
30 };
31
32 auto colRangeSum = [&](int c, int r1, int r2) {
33 return colSum[r2 + 1][c] - colSum[r1][c];
34 };
35
36 int maxSum = INT_MIN;
37
38 for (int r1 = 0; r1 < m; r1++)
39 for (int c1 = 0; c1 < n; c1++)
40 for (int r2 = r1; r2 < m; r2++)
41 for (int c2 = c1; c2 < n; c2++) {
42 int s = rowRangeSum(r1, c1, c2) // top row
43 + rowRangeSum(r2, c1, c2); // bottom row
44
45 if (r2 > r1) {
46 s += colRangeSum(c1, r1 + 1, r2 - 1); // left col (inner)
47 if (c2 > c1)
48 s += colRangeSum(c2, r1 + 1, r2 - 1); // right col (inner)
49 }
50
51 // Subtract double-counted corners if top == bottom
52 if (r1 == r2) {
53 // Already counted correctly — top row only
54 } else if (r2 == r1 + 1) {
55 // No inner rows — just top + bottom
56 }
57
58 if (s > maxSum)
59 maxSum = s;
60 }
61
62 cout << "Max border sum: " << maxSum << endl;
63 return 0;
64}
Each border sum is now O(1), making the total complexity O(m^2 * n^2).
Handling Edge Cases
1// Single cell — border is the cell itself
2// borderSum(mat, 0, 0, 0, 0) = mat[0][0]
3
4// Single row — border is the entire row
5// borderSum(mat, 0, 0, 0, 3) = sum of mat[0][0..3]
6
7// Single column — border is the entire column
8// borderSum(mat, 0, 0, 2, 0) = sum of mat[0..2][0]
9
10// Negative values — the maximum border sum might be a single cell
11// Always consider 1x1 rectangles
Complexity Analysis
| Approach | Time | Space |
| Brute force (compute border each time) | O(m^2 * n^2 * (m+n)) | O(1) |
| Prefix sums (O(1) border sum) | O(m^2 * n^2) | O(m * n) |
Common Pitfalls
Double-counting corner elements: The four corners of the rectangle belong to both a row and a column. When summing the top row + bottom row + left column + right column, the corners are counted twice. Subtract the four corner values, or exclude corners from the column sums.
Not handling the single-row or single-column case: When r1 == r2, the border is just one row. When c1 == c2, the border is just one column. Applying the general formula (top + bottom + left + right) double-counts in these cases.
Using 2D prefix sums (area) instead of row/column prefix sums: The 2D prefix sum gives the sum of all elements in a rectangle (interior included), not just the border. You need separate row and column prefix sums to compute border sums efficiently.
Ignoring negative values in the matrix: If all values are negative, the maximum border sum is the single least-negative cell. The algorithm must consider 1x1 rectangles (single cells) as valid borders.
Integer overflow for large matrices with large values: For a 1000x1000 matrix with values up to 10^6, the border sum can reach 4 * 10^9, exceeding int range. Use long long for the sum variable.
Summary
Enumerate all O(m^2 * n^2) rectangles defined by (top, left, bottom, right)
Use row and column prefix sums to compute each border sum in O(1)
Handle edge cases: single cells, single rows/columns, and double-counted corners
Total optimized complexity: O(m^2 * n^2) time, O(m * n) space
Use long long for sum values to avoid integer overflow on large matrices
