Find the Minimum Area to Cover All Ones II
11 min readJun 23, 2024
Solve it by different cases
Problem
This is the 4th question of the LC weekly 304 contest.
3197. Find the Minimum Area to Cover All Ones II
It looks hard, however, if you solve it by different cases, then it is OK.
Cases:
Since only 3 non overlap rectangles, we only have those 6 cases.
Actually, if we flip the row and col of the input grid, we only need consider about the first 3 cases.
Critical code
int ret = INF;
int this_ret = 0;
int ret_a = 0;
int ret_b = 0;
int ret_c = 0;
int x1, y1, x2, y2;
// case a: 3 rows
if (N>=3){
for (int i = 0; i < N-2; ++i){
x1 = 0, y1 = 0, x2=i, y2 = M -1;
ret_a = get_area(x1, x2, y1, y2);
if (ret_a == 0) continue;
if (ret_a >= ret)continue;
for (int j = i + 1; j < N-1; ++j){
x1 = i+1, y1 = 0, x2=j, y2 = M -1;
ret_b = get_area(x1, x2, y1, y2);
if (ret_b == 0)continue;
this_ret = ret_a + ret_b;
if (this_ret >= ret)continue;
x1 = j+1, y1 = 0, x2=N-1, y2 = M -1;
ret_c = get_area(x1, x2, y1, y2);
if (ret_c == 0)continue;
this_ret += ret_c;
if (this_ret >= ret)continue;
ret = this_ret;
}
}
}
// case b: one row, two columns
if (N >= 2 && M >= 2){
for (int i = 0; i < N-1;++i){
x1 = 0, y1 = 0, x2=i, y2 = M-1;
ret_a = get_area(x1, x2, y1, y2);
if (ret_a == 0)continue;
for (int j = 0; j < M-1;++j){
x1 = i +1, y1 = 0, x2=N-1, y2 = j;
ret_b = get_area(x1, x2, y1, y2);
if (ret_b == 0)continue;
x1 = i+1, y1 = j+1, x2=N-1, y2 = M-1;
ret_c = get_area(x1, x2, y1, y2);
if (ret_c == 0)continue;
this_ret =ret_a + ret_b + ret_c;
if (this_ret < ret)ret = this_ret;
}
}
}
// case c: two columns one row
if (N >= 2 && M >= 2){
for (int i = 0; i < N-1;++i){
x1 = i+1, y1 = 0, x2=N-1, y2 = M-1;
ret_a = get_area(x1, x2, y1, y2);
if (ret_a == 0)continue;
for (int j = 0; j < M-1;++j){
x1 = 0, y1 = 0, x2=i, y2 = j;
ret_b = get_area(x1, x2, y1, y2);
if (ret_b == 0)continue;
x1 = 0, y1 = j+1, x2=i, y2 = M-1;
ret_c = get_area(x1, x2, y1, y2);
if (ret_c == 0)continue;
this_ret =ret_a + ret_b + ret_c;
if (this_ret < ret)ret = this_ret;
}
}
}
return ret;Whole code
Whole code is long, the 2D rang min and max was adjusted from [2]. I believe [1] has a bug which is return maximum value instead of min value, need fix that. We can also precompute the 2D range min and max as the grid size is not large.
const int N = 40;
const int M = 6;
int matrix[N][N];
//int table[N][N][(int)(log2(N) + 1)][(int)(log2(N) + 1)];
int table[N][N][M][M];
int matrix_max[N][N];
int table_max[N][N][M][M];
int matrix_y[N][N];
int table_y[N][N][M][M];
int matrix_y_max[N][N];
int table_y_max[N][N][M][M];
const int INF = 0x3f3f3f3f;
// Function to build the sparse table
void build_sparse_table(int n, int m)
{
// Copy the values of the original matrix
// to the first element of the table
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
table[i][j][0][0] = matrix[i][j];
}
}
// Building the table
for (int k = 1; k <= (int)(log2(n)); k++) {
for (int i = 0; i + (1 << k) - 1 < n; i++) {
for (int j = 0; j < m; j++) {
table[i][j][k][0] = min(
table[i][j][k - 1][0],
table[i + (1 << (k - 1))][j][k - 1][0]);
}
}
}
for (int k = 1; k <= (int)(log2(m)); k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j + (1 << k) - 1 < m; j++) {
table[i][j][0][k] = min(
table[i][j][0][k - 1],
table[i][j + (1 << (k - 1))][0][k - 1]);
}
}
}
for (int k = 1; k <= (int)(log2(n)); k++) {
for (int l = 1; l <= (int)(log2(m)); l++) {
for (int i = 0; i + (1 << k) - 1 < n; i++) {
for (int j = 0; j + (1 << l) - 1 < m; j++) {
table[i][j][k][l] = min(
min(table[i][j][k - 1][l - 1],
table[i + (1 << (k - 1))][j]
[k - 1][l - 1]),
min(table[i][j + (1 << (l - 1))]
[k - 1][l - 1],
table[i + (1 << (k - 1))]
[j + (1 << (l - 1))][k - 1]
[l - 1]));
}
}
}
}
}
// Function to find the maximum value in a submatrix
int rmq_minx(int x1, int y1, int x2, int y2)
{
// log2(x2-x1+1) gives the power of 2
// which is just less than or equal to x2-x1+1
//cout << x1 << " " << y1 <<" "<<x2<<" "<< y2<< endl;
int k = log2(x2 - x1 + 1);
int l = log2(y2 - y1 + 1);
// Lookup the value from the table which is
// the maximum among the 4 submatrices
return min(min(table[x1][y1][k][l],
table[x2 - (1 << k) + 1][y1][k][l]),
min(table[x1][y2 - (1 << l) + 1][k][l],
table[x2 - (1 << k) + 1]
[y2 - (1 << l) + 1][k][l]));
}
// Function to solve the queries
void solve1(int n, int m, vector<vector<int> >& matrix1){
int i = 0;
while (i < n) {
int j = 0;
while (j < m) {
matrix[i][j] = matrix1[i][j];
j++;
}
i++;
}
build_sparse_table(n, m);
}
// Function to build the sparse table_max
void build_sparse_table_max(int n, int m)
{
// Copy the values of the original matrix_max
// to the first element of the table_max
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
table_max[i][j][0][0] = matrix_max[i][j];
}
}
// Building the table_max
for (int k = 1; k <= (int)(log2(n)); k++) {
for (int i = 0; i + (1 << k) - 1 < n; i++) {
for (int j = 0; j < m; j++) {
table_max[i][j][k][0] = min(
table_max[i][j][k - 1][0],
table_max[i + (1 << (k - 1))][j][k - 1][0]);
}
}
}
for (int k = 1; k <= (int)(log2(m)); k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j + (1 << k) - 1 < m; j++) {
table_max[i][j][0][k] = min(
table_max[i][j][0][k - 1],
table_max[i][j + (1 << (k - 1))][0][k - 1]);
}
}
}
for (int k = 1; k <= (int)(log2(n)); k++) {
for (int l = 1; l <= (int)(log2(m)); l++) {
for (int i = 0; i + (1 << k) - 1 < n; i++) {
for (int j = 0; j + (1 << l) - 1 < m; j++) {
table_max[i][j][k][l] = min(
min(table_max[i][j][k - 1][l - 1],
table_max[i + (1 << (k - 1))][j]
[k - 1][l - 1]),
min(table_max[i][j + (1 << (l - 1))]
[k - 1][l - 1],
table_max[i + (1 << (k - 1))]
[j + (1 << (l - 1))][k - 1]
[l - 1]));
}
}
}
}
}
// Function to find the maximum value in a submatrix_max
int rmq_maxx(int x1, int y1, int x2, int y2)
{
// log2(x2-x1+1) gives the power of 2
// which is just less than or equal to x2-x1+1
int k = log2(x2 - x1 + 1);
int l = log2(y2 - y1 + 1);
// Lookup the value from the table_max which is
// the maximum among the 4 submatrices
auto ret = min(min(table_max[x1][y1][k][l],
table_max[x2 - (1 << k) + 1][y1][k][l]),
min(table_max[x1][y2 - (1 << l) + 1][k][l],
table_max[x2 - (1 << k) + 1]
[y2 - (1 << l) + 1][k][l]));
return ret==INF?INF:-ret;
}
// Function to solve the queries
void solve2(int n, int m, vector<vector<int> >& matrix_max1){
int i = 0;
while (i < n) {
int j = 0;
while (j < m) {
matrix_max[i][j] = matrix_max1[i][j];
j++;
}
i++;
}
build_sparse_table_max(n, m);
}
// Driver code
void helper(vector<vector<int>> &matrix1)
{
const int N = matrix1.size(), M = matrix1[0].size();
vector<vector<int>> matrix_max1(N, vector<int>(M));
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
matrix_max1[i][j] = matrix1[i][j] == INF?INF:-matrix1[i][j];
// Function call
solve1(N, M, matrix1);
solve2(N, M, matrix_max1);
//cout << rmq_minx(q[0], q[1], q[2], q[3]) << " ";
//cout << rmq_maxx(q[0], q[1], q[2], q[3]) << endl;
}
// Function to build the sparse table
void build_sparse_table_y(int n, int m)
{
// Copy the values of the original matrix_y
// to the first element of the table
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
table_y[i][j][0][0] = matrix_y[i][j];
}
}
// Building the table
for (int k = 1; k <= (int)(log2(n)); k++) {
for (int i = 0; i + (1 << k) - 1 < n; i++) {
for (int j = 0; j < m; j++) {
table_y[i][j][k][0] = min(
table_y[i][j][k - 1][0],
table_y[i + (1 << (k - 1))][j][k - 1][0]);
}
}
}
for (int k = 1; k <= (int)(log2(m)); k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j + (1 << k) - 1 < m; j++) {
table_y[i][j][0][k] = min(
table_y[i][j][0][k - 1],
table_y[i][j + (1 << (k - 1))][0][k - 1]);
}
}
}
for (int k = 1; k <= (int)(log2(n)); k++) {
for (int l = 1; l <= (int)(log2(m)); l++) {
for (int i = 0; i + (1 << k) - 1 < n; i++) {
for (int j = 0; j + (1 << l) - 1 < m; j++) {
table_y[i][j][k][l] = min(
min(table_y[i][j][k - 1][l - 1],
table_y[i + (1 << (k - 1))][j]
[k - 1][l - 1]),
min(table_y[i][j + (1 << (l - 1))]
[k - 1][l - 1],
table_y[i + (1 << (k - 1))]
[j + (1 << (l - 1))][k - 1]
[l - 1]));
}
}
}
}
}
// Function to find the maximum value in a submatrix_y
int rmq_miny(int x1, int y1, int x2, int y2)
{
// log2(x2-x1+1) gives the power of 2
// which is just less than or equal to x2-x1+1
int k = log2(x2 - x1 + 1);
int l = log2(y2 - y1 + 1);
// Lookup the value from the table_y which is
// the maximum among the 4 submatrices
return min(min(table_y[x1][y1][k][l],
table_y[x2 - (1 << k) + 1][y1][k][l]),
min(table_y[x1][y2 - (1 << l) + 1][k][l],
table_y[x2 - (1 << k) + 1]
[y2 - (1 << l) + 1][k][l]));
}
// Function to solve_y the queries
void solve_y1(int n, int m, vector<vector<int> >& matrix_y1){
int i = 0;
while (i < n) {
int j = 0;
while (j < m) {
matrix_y[i][j] = matrix_y1[i][j];
j++;
}
i++;
}
build_sparse_table_y(n, m);
}
// Function to build the sparse table_y_max
void build_sparse_table_y_max(int n, int m)
{
// Copy the values of the original matrix_y_max
// to the first element of the table_y_max
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
table_y_max[i][j][0][0] = matrix_y_max[i][j];
}
}
// Building the table_y_max
for (int k = 1; k <= (int)(log2(n)); k++) {
for (int i = 0; i + (1 << k) - 1 < n; i++) {
for (int j = 0; j < m; j++) {
table_y_max[i][j][k][0] = min(
table_y_max[i][j][k - 1][0],
table_y_max[i + (1 << (k - 1))][j][k - 1][0]);
}
}
}
for (int k = 1; k <= (int)(log2(m)); k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j + (1 << k) - 1 < m; j++) {
table_y_max[i][j][0][k] = min(
table_y_max[i][j][0][k - 1],
table_y_max[i][j + (1 << (k - 1))][0][k - 1]);
}
}
}
for (int k = 1; k <= (int)(log2(n)); k++) {
for (int l = 1; l <= (int)(log2(m)); l++) {
for (int i = 0; i + (1 << k) - 1 < n; i++) {
for (int j = 0; j + (1 << l) - 1 < m; j++) {
table_y_max[i][j][k][l] = min(
min(table_y_max[i][j][k - 1][l - 1],
table_y_max[i + (1 << (k - 1))][j]
[k - 1][l - 1]),
min(table_y_max[i][j + (1 << (l - 1))]
[k - 1][l - 1],
table_y_max[i + (1 << (k - 1))]
[j + (1 << (l - 1))][k - 1]
[l - 1]));
}
}
}
}
}
// Function to find the maximum value in a submatrix_y_max
int rmq_maxy(int x1, int y1, int x2, int y2)
{
// log2(x2-x1+1) gives the power of 2
// which is just less than or equal to x2-x1+1
int k = log2(x2 - x1 + 1);
int l = log2(y2 - y1 + 1);
// Lookup the value from the table_y_max which is
// the maximum among the 4 submatrices
auto ret = min(min(table_y_max[x1][y1][k][l],
table_y_max[x2 - (1 << k) + 1][y1][k][l]),
min(table_y_max[x1][y2 - (1 << l) + 1][k][l],
table_y_max[x2 - (1 << k) + 1]
[y2 - (1 << l) + 1][k][l]));
return ret==INF?INF:-ret;
}
// Function to solve_y the queries
void solve_y2(int n, int m, vector<vector<int> >& matrix_y_max1){
int i = 0;
while (i < n) {
int j = 0;
while (j < m) {
matrix_y_max[i][j] = matrix_y_max1[i][j];
j++;
}
i++;
}
build_sparse_table_y_max(n, m);
}
// Driver code
void helper_y(vector<vector<int>> &matrix_y1)
{
const int N = matrix_y1.size(), M = matrix_y1[0].size();
vector<vector<int>> matrix_y_max1(N, vector<int>(M));
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
matrix_y_max1[i][j] = matrix_y1[i][j] == INF?INF:-matrix_y1[i][j];
// Function call
solve_y1(N, M, matrix_y1);
solve_y2(N, M, matrix_y_max1);
//cout << rmq_miny(q[0], q[1], q[2], q[3]) << " ";
//cout << rmq_maxy(q[0], q[1], q[2], q[3]) << endl;
}
class Solution {
public:
int get_area(int x1, int x2, int y1, int y2){
auto min_x = rmq_minx(x1, y1, x2, y2);
if (min_x == INF) return 0;
auto max_x = rmq_maxx(x1, y1, x2, y2);
auto min_y = rmq_miny(x1, y1, x2, y2);
auto max_y = rmq_maxy(x1, y1, x2, y2);
return (max_x - min_x + 1) * (max_y - min_y + 1);
}
int _minimumSum(vector<vector<int>>& grid) {
const int N = grid.size(), M = grid[0].size();
vector<vector<int>> matrix1(N, vector<int>(M));
vector<vector<int>> matrix_y1(N, vector<int>(M));
memset(table, 0, sizeof table);
memset(table_max, 0, sizeof table_max);
memset(table_y, 0, sizeof table_y);
memset(table_y_max, 0, sizeof table_y_max);
memset(matrix, 0, sizeof matrix);
memset(matrix_max, 0, sizeof matrix_max);
memset(matrix_y, 0, sizeof matrix_y);
memset(matrix_y_max, 0, sizeof matrix_y_max);
for(int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
if (grid[i][j] == 1){
matrix1[i][j] = i;
matrix_y1[i][j] = j;
} else {
matrix1[i][j] = INF;
matrix_y1[i][j] = INF;
}
}
}
helper(matrix1);
helper_y(matrix_y1);
int ret = INF;
int this_ret = 0;
int ret_a = 0;
int ret_b = 0;
int ret_c = 0;
int x1, y1, x2, y2;
// 3 rows
if (N>=3){
for (int i = 0; i < N-2; ++i){
x1 = 0, y1 = 0, x2=i, y2 = M -1;
ret_a = get_area(x1, x2, y1, y2);
if (ret_a == 0) continue;
if (ret_a >= ret)continue;
for (int j = i + 1; j < N-1; ++j){
x1 = i+1, y1 = 0, x2=j, y2 = M -1;
ret_b = get_area(x1, x2, y1, y2);
if (ret_b == 0)continue;
this_ret = ret_a + ret_b;
if (this_ret >= ret)continue;
x1 = j+1, y1 = 0, x2=N-1, y2 = M -1;
ret_c = get_area(x1, x2, y1, y2);
if (ret_c == 0)continue;
this_ret += ret_c;
if (this_ret >= ret)continue;
ret = this_ret;
}
}
}
// one row, two columns
if (N >= 2 && M >= 2){
for (int i = 0; i < N-1;++i){
x1 = 0, y1 = 0, x2=i, y2 = M-1;
ret_a = get_area(x1, x2, y1, y2);
if (ret_a == 0)continue;
for (int j = 0; j < M-1;++j){
x1 = i +1, y1 = 0, x2=N-1, y2 = j;
ret_b = get_area(x1, x2, y1, y2);
if (ret_b == 0)continue;
x1 = i+1, y1 = j+1, x2=N-1, y2 = M-1;
ret_c = get_area(x1, x2, y1, y2);
if (ret_c == 0)continue;
this_ret =ret_a + ret_b + ret_c;
if (this_ret < ret)ret = this_ret;
}
}
}
// two columns one row
if (N >= 2 && M >= 2){
for (int i = 0; i < N-1;++i){
x1 = i+1, y1 = 0, x2=N-1, y2 = M-1;
ret_a = get_area(x1, x2, y1, y2);
if (ret_a == 0)continue;
for (int j = 0; j < M-1;++j){
x1 = 0, y1 = 0, x2=i, y2 = j;
ret_b = get_area(x1, x2, y1, y2);
if (ret_b == 0)continue;
x1 = 0, y1 = j+1, x2=i, y2 = M-1;
ret_c = get_area(x1, x2, y1, y2);
if (ret_c == 0)continue;
this_ret =ret_a + ret_b + ret_c;
if (this_ret < ret)ret = this_ret;
}
}
}
return ret;
}
int minimumSum(vector<vector<int>>& grid) {
auto ret = _minimumSum(grid);
const int n = grid.size(), m = grid[0].size();
vector<vector<int>> new_grid(m, vector<int>(n, 0));
for (int i = 0; i <n;++i)
for (int j = 0; j < m;++j){
new_grid[j][i] = grid[i][j];
}
ret = min(ret, _minimumSum(new_grid));
return ret;
}
};Reference
[1]https://www.geeksforgeeks.org/2d-range-minimum-query-in-o1/
