LeetCode’s Problem 3197 (Hard) is one of those grid-based problems that force us to think deeply about partitioning, optimization, and dynamic computation. Many developers struggle with finding efficient solutions because it requires geometry + DP + prefix sums reasoning.
Problem Statement (LeetCode 3197)
We are given a 2D binary grid. We need to find 3 non-overlapping rectangles (aligned with grid axes, non-zero area, allowed to touch) such that all 1s are covered and the sum of areas is minimized.
👉 Example 1:
Input: grid = [[1,0,1],
[1,1,1]]
Output: 5
Explanation:
- Cover
(0,0)and(1,0)→ rectangle of area 2 - Cover
(0,2)and(1,2)→ rectangle of area 2 - Cover
(1,1)alone → rectangle of area 1
Total area = 5
💡 Key Insights
Bounding Rectangles: To cover all1s in a region with one rectangle, we can just compute the smallest bounding rectangle of the 1’s.
Recursive Splits: To cover with 2 rectangles, we try partitioning by row or column.- Dynamic Programming + Prefix Sums:
- Use row and column suffix sums to quickly check presence of
1s in a region.
Build helper functions:
f1(...)→ Minimum area with 1 rectangle
f2(...)→ Minimum area with 2 rectangles
Finally combine for 3 rectangles using partitions.
This hierarchical breakdown (1 → 2 → 3 rectangles) avoids brute force and gives a much faster solution.
🧩 Step-by-Step Solution Strategy
- Precompute Suffix Sums:
row_sfx[i][j]: Number of1s in rowifrom columnjto end.
col_sfx[j][i]: Number of1s in columnjfrom rowito bottom.
- Function
f1:
- Shrinks boundaries until we enclose all
1s → returns area of bounding box.
- Function
f2:
- Try splitting the region into 2 parts (horizontal or vertical).
- Minimize sum of
f1for each partition.
- Final Combination:
- For 3 rectangles, try splitting first into
(1 rect + 2 rect)or(2 rect + 1 rect)partitions. - Iterate over all row and column cuts.
🖥️ C++ Implementation (Efficient Solution)
Here’s the solution you shared, polished for readability:
class Solution {
public:
vector<vector<int>> row_sfx, col_sfx;
int get_row_count(int i, int l, int r) {
return row_sfx[i][l] - row_sfx[i][r + 1];
}
int get_col_count(int j, int t, int b) {
return col_sfx[j][t] - col_sfx[j][b + 1];
}
// Cover all 1s with 1 rectangle
int f1(int si, int ei, int sj, int ej) {
while (si < ei && !get_row_count(si, sj, ej)) si++;
while (ei > si && !get_row_count(ei, sj, ej)) ei--;
while (sj < ej && !get_col_count(sj, si, ei)) sj++;
while (ej > sj && !get_col_count(ej, si, ei)) ej--;
int h = max(0, ei - si + 1), w = max(0, ej - sj + 1);
return h * w;
}
// Cover all 1s with 2 rectangles
int f2(int si, int ei, int sj, int ej) {
int res = f1(si, ei, sj, ej);
for (int i = si; i < ei; i++)
res = min(res, f1(si, i, sj, ej) + f1(i + 1, ei, sj, ej));
for (int j = sj; j < ej; j++)
res = min(res, f1(si, ei, sj, j) + f1(si, ei, j + 1, ej));
return res;
}
int minimumSum(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
row_sfx.assign(n, vector<int>(m + 1));
col_sfx.assign(m, vector<int>(n + 1));
// Precompute suffix sums
for (int i = 0; i < n; i++)
for (int j = m - 1; j >= 0; j--)
row_sfx[i][j] = grid[i][j] + row_sfx[i][j + 1];
for (int j = 0; j < m; j++)
for (int i = n - 1; i >= 0; i--)
col_sfx[j][i] = grid[i][j] + col_sfx[j][i + 1];
int ans = n * m;
// Partition rows
for (int i = 0; i < n - 1; i++) {
ans = min(ans, f1(0, i, 0, m - 1) + f2(i + 1, n - 1, 0, m - 1));
ans = min(ans, f2(0, i, 0, m - 1) + f1(i + 1, n - 1, 0, m - 1));
}
// Partition cols
for (int j = 0; j < m - 1; j++) {
ans = min(ans, f1(0, n - 1, 0, j) + f2(0, n - 1, j + 1, m - 1));
ans = min(ans, f2(0, n - 1, 0, j) + f1(0, n - 1, j + 1, m - 1));
}
return ans;
}
};
🐍 Python Implementation
class Solution:
def minimumSum(self, grid):
n, m = len(grid), len(grid[0])
# Precompute suffix sums
row_sfx = [[0]*(m+1) for _ in range(n)]
col_sfx = [[0]*(n+1) for _ in range(m)]
for i in range(n):
for j in range(m-1, -1, -1):
row_sfx[i][j] = grid[i][j] + row_sfx[i][j+1]
for j in range(m):
for i in range(n-1, -1, -1):
col_sfx[j][i] = grid[i][j] + col_sfx[j][i+1]
def get_row_count(i, l, r):
return row_sfx[i][l] - row_sfx[i][r+1]
def get_col_count(j, t, b):
return col_sfx[j][t] - col_sfx[j][b+1]
def f1(si, ei, sj, ej):
while si < ei and all(get_row_count(si, sj, ej) == 0): si += 1
while ei > si and all(get_row_count(ei, sj, ej) == 0): ei -= 1
while sj < ej and all(get_col_count(sj, si, ei) == 0): sj += 1
while ej > sj and all(get_col_count(ej, si, ei) == 0): ej -= 1
return max(0, ei-si+1) * max(0, ej-sj+1)
def f2(si, ei, sj, ej):
res = f1(si, ei, sj, ej)
for i in range(si, ei):
res = min(res, f1(si, i, sj, ej) + f1(i+1, ei, sj, ej))
for j in range(sj, ej):
res = min(res, f1(si, ei, sj, j) + f1(si, ei, j+1, ej))
return res
ans = n*m
for i in range(n-1):
ans = min(ans, f1(0, i, 0, m-1) + f2(i+1, n-1, 0, m-1))
ans = min(ans, f2(0, i, 0, m-1) + f1(i+1, n-1, 0, m-1))
for j in range(m-1):
ans = min(ans, f1(0, n-1, 0, j) + f2(0, n-1, j+1, m-1))
ans = min(ans, f2(0, n-1, 0, j) + f1(0, n-1, j+1, m-1))
return ans
☕ Java Implementation
class Solution {
int[][] row_sfx, col_sfx;
int getRowCount(int i, int l, int r) {
return row_sfx[i][l] - row_sfx[i][r+1];
}
int getColCount(int j, int t, int b) {
return col_sfx[j][t] - col_sfx[j][b+1];
}
int f1(int si, int ei, int sj, int ej) {
while (si < ei && getRowCount(si, sj, ej) == 0) si++;
while (ei > si && getRowCount(ei, sj, ej) == 0) ei--;
while (sj < ej && getColCount(sj, si, ei) == 0) sj++;
while (ej > sj && getColCount(ej, si, ei) == 0) ej--;
return Math.max(0, ei-si+1) * Math.max(0, ej-sj+1);
}
int f2(int si, int ei, int sj, int ej) {
int res = f1(si, ei, sj, ej);
for (int i = si; i < ei; i++)
res = Math.min(res, f1(si, i, sj, ej) + f1(i+1, ei, sj, ej));
for (int j = sj; j < ej; j++)
res = Math.min(res, f1(si, ei, sj, j) + f1(si, ei, j+1, ej));
return res;
}
public int minimumSum(int[][] grid) {
int n = grid.length, m = grid[0].length;
row_sfx = new int[n][m+1];
col_sfx = new int[m][n+1];
for (int i = 0; i < n; i++)
for (int j = m-1; j >= 0; j--)
row_sfx[i][j] = grid[i][j] + row_sfx[i][j+1];
for (int j = 0; j < m; j++)
for (int i = n-1; i >= 0; i--)
col_sfx[j][i] = grid[i][j] + col_sfx[j][i+1];
int ans = n*m;
for (int i = 0; i < n-1; i++) {
ans = Math.min(ans, f1(0, i, 0, m-1) + f2(i+1, n-1, 0, m-1));
ans = Math.min(ans, f2(0, i, 0, m-1) + f1(i+1, n-1, 0, m-1));
}
for (int j = 0; j < m-1; j++) {
ans = Math.min(ans, f1(0, n-1, 0, j) + f2(0, n-1, j+1, m-1));
ans = Math.min(ans, f2(0, n-1, 0, j) + f1(0, n-1, j+1, m-1));
}
return ans;
}
}
⚡ Complexity Analysis
- Precomputation: O(n·m)
- Each
f1: O(1) after shrinking boundaries - Each
f2: O(n + m) (splitting rows + cols) - Final loops: O(n + m) partitions
- ✅ Overall complexity: O(n² + m²) (efficient for
n, m ≤ 30)
🎯 Takeaways
- This problem is a great example of combining geometry + DP partitioning + prefix sums.
- It teaches us how to reduce a seemingly exponential partition problem into manageable recursive functions (
f1,f2, and final combo). - Having multiple language implementations makes the logic accessible to more developers.
SOCIAL SHARE CARD GENERATOR