Case 1 — Top block + two bottom blocks (bottom split vertically):
 
+---------+
|    1    |
+---+-----+
| 2 |  3  |
+---+-----+
 
Case 2 — Left block + two right blocks (right split horizontally):
 
+---+-----+
| 1 |  2  |
|   |-----|
|   |  3  |
+---+-----+
 
Case 3 — Right block + two left blocks (mirror of Case 2):
 
+-----+---+
| 2   | 1 |
|-----|   |
| 3   |   |
+-----+---+
 
Case 4 — Bottom block + two top blocks (mirror of Case 1):
 
+---+-----+
| 2 |  3  |
+---+-----+
|    1    |
+---------+
 
Case 5 — Three horizontal strips:
 
+--------+
|   1    |
+--------+
|   2    |
+--------+
|   3    |
+--------+
 
Case 6 — Three vertical strips:
 
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+

Approach

Implement a helper areaOfOnes(grid, st_i, en_i, st_j, en_j) that returns the area of the smallest rectangle that covers all 1's inside the inclusive submatrix [st_i..en_i] x [st_j..en_j] (or 0 if none).
Enumerate the standard partition templates (top/bottom split with a bottom split into two, left/right split with right split into two, mirrored variants, three horizontal strips, three vertical strips). For each partition, call the helper for the three parts and keep the minimum total area found.
This reuses the O(size_of_submatrix) scanning helper instead of constructing arbitrary rectangles, making it much faster than the full brute-force enumeration.

Code

[{"language":"C++","code":"class Solution {\npublic:\n  int minimumSum(vector<vector<int>>& grid) {\n    int m = grid.

Related Tags

Continue Practicing