| 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.size(), n = grid[0].size();\n    int ans = numeric_limits<int>::max();\n    int one, two, three;\n\n    // 1) Top block + two blocks in the bottom row (split by a vertical line)\n    for (int i = 0; i < m; ++i) {\n      one = areaOfOnes(grid, 0, i, 0, n - 1);\n      for (int j = 0; j < n; ++j) {\n        two = areaOfOnes(grid, i + 1, m - 1, 0, j);\n        three = areaOfOnes(grid, i + 1, m - 1, j + 1, n - 1);\n        ans = min(ans, one + two + three);\n      }\n    }\n\n    // 2) Left block + two blocks on the right (split by a horizontal line)\n    for (int j = 0; j < n; ++j) {\n      one = areaOfOnes(grid, 0, m - 1, 0, j);\n      for (int i = 0; i < m; ++i) {\n        two = areaOfOnes(grid, 0, i, j + 1, n - 1);\n        three = areaOfOnes(grid, i + 1, m - 1, j + 1, n - 1);\n        ans = min(ans, one + two + three);\n      }\n    }\n\n    // 3) Right block + two blocks on the left (mirror of previous)\n    for (int j = n - 1; j >= 0; --j) {\n      one = areaOfOnes(grid, 0, m - 1, j + 1, n - 1);\n      for (int i = 0; i < m; ++i) {\n        two = areaOfOnes(grid, 0, i, 0, j);\n        three = areaOfOnes(grid, i + 1, m - 1, 0, j);\n        ans = min(ans, one + two + three);\n      }\n    }\n\n    // 4) Bottom block + two blocks on the top (mirror of 1)\n    for (int i = m - 1; i >= 0; --i) {\n      one = areaOfOnes(grid, i + 1, m - 1, 0, n - 1);\n      for (int j = 0; j < n; ++j) {\n        two = areaOfOnes(grid, 0, i, 0, j);\n        three = areaOfOnes(grid, 0, i, j + 1, n - 1);\n        ans = min(ans, one + two + three);\n      }\n    }\n\n    // 5) Three horizontal strips\n    for (int i = 0; i < m; ++i) {\n      for (int j = i + 1; j < m; ++j) {\n        one = areaOfOnes(grid, 0, i, 0, n - 1);\n        two = areaOfOnes(grid, i + 1, j, 0, n - 1);\n        three = areaOfOnes(grid, j + 1, m - 1, 0, n - 1);\n        ans = min(ans, one + two + three);\n      }\n    }\n\n    // 6) Three vertical strips\n    for (int i = 0; i < n; ++i) {\n      for (int j = i + 1; j < n; ++j) {\n

Related Tags

Continue Practicing