Dada una array binaria. El problema es encontrar la subarray rectangular de mayor área con igual número de 1 y 0. Ejemplos:
Input : mat[][] = { {0, 0, 1, 1},
{0, 1, 1, 0},
{1, 1, 1, 0},
{1, 0, 0, 1} }
Output : 8 sq. units
(Top, left): (0, 0)
(Bottom, right): (3, 1)
Input : mat[][] = { {0, 0, 1, 1},
{0, 1, 1, 1} }
Output : 6 sq. units
La solución ingenua para este problema es verificar cada rectángulo posible en una array 2D dada contando el número total de 1 y 0 en ese rectángulo. Esta solución requiere 4 bucles anidados y la complejidad de tiempo de esta solución sería O(n^4).
Una solución eficiente se basa en la subarray rectangular más grande cuya suma es 0 , lo que reduce la complejidad del tiempo a O (n ^ 3). En primer lugar, considere cada ‘0’ en la array como ‘-1’. Ahora, la idea es reducir el problema a una array 1-D. Arreglamos las columnas izquierda y derecha una por una y encontramos el subarreglo más grande con filas contiguas de suma 0 para cada par de columnas izquierda y derecha. Básicamente, encontramos números de fila superior e inferior (que tienen suma cero) para cada par de columnas fijas izquierda y derecha. Para encontrar los números de las filas superior e inferior, calcule la suma de los elementos en cada fila de izquierda a derecha y almacene estas sumas en una array, digamos temp[].
Entonces temp[i] indica la suma de los elementos de izquierda a derecha en la fila i. Si encontramos el subarreglo más grande con suma 0 en temp[], podemos obtener las posiciones de índice de la subarray rectangular con suma igual a 0 (es decir, con el mismo número de 1 y 0). Con este proceso podemos encontrar la subarray rectangular de área más grande con una suma igual a 0 (es decir, que tenga el mismo número de 1 y 0). Podemos usar la técnica Hashing para encontrar el subarreglo de longitud máxima con una suma igual a 0 en un arreglo 1-D en tiempo O(n).
Implementación:
CPP
// C++ implementation to find largest area rectangular
// submatrix with equal number of 1's and 0's
#include <bits/stdc++.h>
using namespace std;
#define MAX_ROW 10
#define MAX_COL 10
// This function basically finds largest 0
// sum subarray in arr[0..n-1]. If 0 sum
// does't exist, then it returns false. Else
// it returns true and sets starting and
// ending indexes as start and end.
bool subArrWithSumZero(int arr[], int &start,
int &end, int n)
{
// to store cumulative sum
int sum[n];
// Initialize all elements of sum[] to 0
memset(sum, 0, sizeof(sum));
// map to store the indexes of sum
unordered_map<int, int> um;
// build up the cumulative sum[] array
sum[0] = arr[0];
for (int i=1; i<n; i++)
sum[i] = sum[i-1] + arr[i];
// to store the maximum length subarray
// with sum equal to 0
int maxLen = 0;
// traverse to the sum[] array
for (int i=0; i<n; i++)
{
// if true, then there is a subarray
// with sum equal to 0 from the
// beginning up to index 'i'
if (sum[i] == 0)
{
// update the required variables
start = 0;
end = i;
maxLen = (i+1);
}
// else if true, then sum[i] has not
// seen before in 'um'
else if (um.find(sum[i]) == um.end())
um[sum[i]] = i;
// sum[i] has been seen before in the
// unordered_map 'um'
else
{
// if previous subarray length is smaller
// than the current subarray length, then
// update the required variables
if (maxLen < (i-um[sum[i]]))
{
maxLen = (i-um[sum[i]]);
start = um[sum[i]] + 1;
end = i;
}
}
}
// if true, then there is no
// subarray with sum equal to 0
if (maxLen == 0)
return false;
// else return true
return true;
}
// function to find largest area rectangular
// submatrix with equal number of 1's and 0's
void maxAreaRectWithSumZero(int mat[MAX_ROW][MAX_COL],
int row, int col)
{
// to store intermediate values
int temp[row], startRow, endRow;
// to store the final outputs
int finalLeft, finalRight, finalTop, finalBottom;
finalLeft = finalRight = finalTop = finalBottom = -1;
int maxArea = 0;
// Set the left column
for (int left = 0; left < col; left++)
{
// Initialize all elements of temp as 0
memset(temp, 0, sizeof(temp));
// Set the right column for the left column
// set by outer loop
for (int right = left; right < col; right++)
{
// Calculate sum between current left
// and right for every row 'i'
// consider value '1' as '1' and
// value '0' as '-1'
for (int i=0; i<row; i++)
temp[i] += mat[i][right] ? 1 : -1;
// Find largest subarray with 0 sum in
// temp[]. The subArrWithSumZero() function
// also sets values of finalTop, finalBottom,
// finalLeft and finalRight if there exists
// a subarray with sum 0 in temp
if (subArrWithSumZero(temp, startRow, endRow, row))
{
int area = (right - left + 1) *
(endRow - startRow + 1);
// Compare current 'area' with previous area
// and accordingly update final values
if (maxArea < area)
{
finalTop = startRow;
finalBottom = endRow;
finalLeft = left;
finalRight = right;
maxArea = area;
}
}
}
}
// if true then there is no rectangular submatrix
// with equal number of 1's and 0's
if (maxArea == 0)
cout << "No such rectangular submatrix exists:";
// displaying the top left and bottom right boundaries
// with the area of the rectangular submatrix
else
{
cout << "(Top, Left): "
<< "(" << finalTop << ", " << finalLeft
<< ")" << endl;
cout << "(Bottom, Right): "
<< "(" << finalBottom << ", " << finalRight
<< ")" << endl;
cout << "Area: " << maxArea << " sq.units";
}
}
// Driver program to test above
int main()
{
int mat[MAX_ROW][MAX_COL] = { {0, 0, 1, 1},
{0, 1, 1, 0},
{1, 1, 1, 0},
{1, 0, 0, 1} };
int row = 4, col = 4;
maxAreaRectWithSumZero(mat, row, col);
return 0;
}
(Top, Left): (0, 0) (Bottom, Right): (3, 1) Area: 8 sq.units
Complejidad de tiempo: O(n 3 ) Espacio auxiliar: O(n) Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA