Dada una array N*N que contiene solo 0 y 1, la tarea es contar el número de subarrays que contienen solo 1.
Ejemplos:
Input : arr[][] = {{1, 1, 1},
{1, 1, 1},
{1, 1, 1}}
Output : 36
Explanation: All the possible submatrices will have only 1s.
Since, there are 36 submatrices in total, ans = 36
Input : {{1, 1, 1},
{1, 0, 1},
{1, 1, 1}}
Output : 20
Para simplificar, diremos que una subarray comienza desde un índice (R, C) si ese índice en particular es su esquina superior izquierda.
Una solución simple será generar todas las subarrays posibles y luego verificar si todos los valores dentro de ellas son 1. Si para una subarray, todos los elementos son uno, incrementamos el valor de la respuesta final en uno. La complejidad temporal del enfoque anterior es O(n 6 ).
Mejor enfoque : para optimizar el proceso, para cada índice de la array, intentaremos encontrar el número de subarrays a partir de ese índice que tenga solo 1.
Nuestro primer paso para resolver este problema es crear una array ‘p_arr’.
Para cada índice (R, C), si arr[R][C] es igual a 1, entonces en p_arr[R][C], almacenaremos el número de 1 a la derecha de la celda (R, C) a lo largo de la fila ‘R’ antes de que encontremos el primer cero o el final de la array más 1.
Si arr[R][C] es igual a cero, p_arr[R][C] también es igual a cero.
Para crear esta array, utilizaremos la siguiente relación de recurrencia.
IF arr[R][C] is not 0
p_arr[R][C] = p_arr[R][C+1] + 1
ELSE
p_arr[R][C] = 0
arr[][] = {{1, 0, 1, 1},
{0, 1, 0, 1},
{1, 1, 1, 0},
{1, 0, 1, 1}}
p_arr[][] for above will look like
{{1, 0, 2, 1},
{0, 1, 0, 1},
{3, 2, 1, 0},
{1, 0, 2, 1}}
Una vez que tengamos la array p_arr requerida , procederemos al siguiente paso. Mire la array ‘p_arr’ en forma de columna. Si estamos procesando la j -ésima columna de la array p_arr, entonces para cada elemento ‘i’ de esta columna, intentaremos encontrar el número de subarrays comenzando desde la celda (i, j) con todos 1s.
Para ello, podemos utilizar la estructura de datos de la pila .
Algoritmo :
- Inicialice una pila ‘q’ para almacenar el valor de los elementos que se empujan junto con el recuento (C ij ) del número de elementos que se empujaron en esta pila con un valor estrictamente mayor que el valor del elemento actual. Usaremos un par para unir los dos datos.
Inicialice una variable ‘to_sum’ con 0. En cada paso, esta variable se actualiza para almacenar el número de subarrays con todos los 1 a partir del elemento que se empuja en ese paso. Por lo tanto, usando ‘to_sum’, actualizamos el conteo del número de subarrays con todos 1 en cada paso. - Para una columna ‘j’, en cualquier paso ‘i’, nos prepararemos para insertar p_arr[i][j] en la pila. Sea Q t el elemento superior de la pila y C t represente el número de elementos colocados previamente en la pila con un valor mayor que el elemento superior de la pila. Antes de insertar un elemento ‘p_arr[i][j]’ en la pila, mientras la pila no esté vacía o el elemento superior sea mayor que el número que se va a insertar, siga extrayendo el elemento superior de la pila y al mismo tiempo actualice to_sum como to_sum += (C t + 1) * (Q t – p_arr[i][j]) . Sea C i,representan el número de elementos mayor que el elemento actual que se colocó en esta pila anteriormente. También necesitamos hacer un seguimiento de C i, j . Por lo tanto, antes de extraer un elemento, actualizamos C i, j como C i, j += C t junto con to_sum.
- Actualizamos la respuesta como ans += to_sum.
- Finalmente, empujamos ese elemento en la pila después de emparejarlo con C i, j .
Cree la array de prefijos en O(n 2 ) y para cada columna, insertamos un elemento en la pila o lo extraemos solo una vez. Por tanto, la complejidad temporal de este algoritmo es O(n 2 ).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count number of
// sub-matrices with all 1s
#include <iostream>
#include <stack>
using namespace std;
#define n 3
// Function to find required prefix-count for
// each row from right to left
void findPrefixCount(int p_arr[][n], bool arr[][n])
{
for (int i = 0; i < n; i++) {
for (int j = n - 1; j >= 0; j--) {
if (!arr[i][j])
continue;
if (j != n - 1)
p_arr[i][j] += p_arr[i][j + 1];
p_arr[i][j] += (int)arr[i][j];
}
}
}
// Function to count the number of
// sub-matrices with all 1s
int matrixAllOne(bool arr[][n])
{
// Array to store required prefix count of
// 1s from right to left for boolean array
int p_arr[n][n] = { 0 };
findPrefixCount(p_arr, arr);
// variable to store the final answer
int ans = 0;
/* Loop to evaluate each column of
the prefix matrix uniquely.
For each index of a column we will try to
determine the number of sub-matrices
starting from that index
and has all 1s */
for (int j = 0; j < n; j++) {
int i = n - 1;
/* Stack to store elements and the count
of the numbers they popped
First part of pair will be the
value of inserted element.
Second part will be the count
of the number of elements pushed
before with a greater value */
stack<pair<int, int> > q;
// variable to store the number of
// submatrices with all 1s
int to_sum = 0;
while (i >= 0) {
int c = 0;
while (q.size() != 0 and q.top().first > p_arr[i][j]) {
to_sum -= (q.top().second + 1) *
(q.top().first - p_arr[i][j]);
c += q.top().second + 1;
q.pop();
}
to_sum += p_arr[i][j];
ans += to_sum;
q.push({ p_arr[i][j], c });
i--;
}
}
return ans;
}
// Driver Code
int main()
{
bool arr[][n] = { { 1, 1, 0 },
{ 1, 0, 1 },
{ 0, 1, 1 } };
cout << matrixAllOne(arr);
return 0;
}
Java
// Java program to count number of
// sub-matrices with all 1s
import java.util.*;
class GFG
{
static int n = 3;
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to find required prefix-count for
// each row from right to left
static void findPrefixCount(int p_arr[][],
boolean arr[][])
{
for (int i = 0; i < n; i++)
{
for (int j = n - 1; j >= 0; j--)
{
if (!arr[i][j])
continue;
if (j != n - 1)
p_arr[i][j] += p_arr[i][j + 1];
p_arr[i][j] += arr[i][j] == true ? 1 : 0;
}
}
}
// Function to count the number of
// sub-matrices with all 1s
static int matrixAllOne(boolean arr[][])
{
// Array to store required prefix count of
// 1s from right to left for boolean array
int [][]p_arr = new int[n][n];
findPrefixCount(p_arr, arr);
// variable to store the final answer
int ans = 0;
/* Loop to evaluate each column of
the prefix matrix uniquely.
For each index of a column we will try to
determine the number of sub-matrices
starting from that index
and has all 1s */
for (int j = 0; j < n; j++)
{
int i = n - 1;
/* Stack to store elements and the count
of the numbers they popped
First part of pair will be the
value of inserted element.
Second part will be the count
of the number of elements pushed
before with a greater value */
Stack<pair> q = new Stack<pair>();
// variable to store the number of
// submatrices with all 1s
int to_sum = 0;
while (i >= 0)
{
int c = 0;
while (q.size() != 0 &&
q.peek().first > p_arr[i][j])
{
to_sum -= (q.peek().second + 1) *
(q.peek().first - p_arr[i][j]);
c += q.peek().second + 1;
q.pop();
}
to_sum += p_arr[i][j];
ans += to_sum;
q.add(new pair(p_arr[i][j], c));
i--;
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
boolean arr[][] = { { true, true, false },
{ true, false, true },
{ false, true, true } };
System.out.println(matrixAllOne(arr));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to count the number # of sub-matrices with all 1s # Function to find required prefix-count # for each row from right to left def findPrefixCount(p_arr, arr): for i in range(0, n): for j in range(n - 1, -1, -1): if not arr[i][j]: continue if j != n - 1: p_arr[i][j] += p_arr[i][j + 1] p_arr[i][j] += arr[i][j] # Function to count the number of # sub-matrices with all 1s def matrixAllOne(arr): # Array to store required prefix count of # 1s from right to left for boolean array p_arr = [[0 for i in range(n)] for j in range(n)] findPrefixCount(p_arr, arr) # variable to store the final answer ans = 0 # Loop to evaluate each column of # the prefix matrix uniquely. # For each index of a column we will try to # determine the number of sub-matrices # starting from that index and has all 1s for j in range(0, n): i = n - 1 # Stack to store elements and the count # of the numbers they popped # First part of pair will be the # value of inserted element. # Second part will be the count # of the number of elements pushed # before with a greater value */ q = [] # variable to store the number of # submatrices with all 1s to_sum = 0 while i >= 0: c = 0 while len(q) != 0 and q[-1][0] > p_arr[i][j]: to_sum -= (q[-1][1] + 1) * \ (q[-1][0] - p_arr[i][j]) c += q[-1][1] + 1 q.pop() to_sum += p_arr[i][j] ans += to_sum q.append((p_arr[i][j], c)) i -= 1 return ans # Driver Code if __name__ == "__main__": arr = [[1, 1, 0], [1, 0, 1], [0, 1, 1]] n = 3 print(matrixAllOne(arr)) # This code is contributed by Rituraj Jain
C#
// C# program to count number of
// sub-matrices with all 1s
using System;
using System.Collections.Generic;
class GFG
{
static int n = 3;
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to find required prefix-count for
// each row from right to left
static void findPrefixCount(int [,]p_arr,
Boolean [,]arr)
{
for (int i = 0; i < n; i++)
{
for (int j = n - 1; j >= 0; j--)
{
if (!arr[i, j])
continue;
if (j != n - 1)
p_arr[i, j] += p_arr[i, j + 1];
p_arr[i, j] += arr[i, j] == true ? 1 : 0;
}
}
}
// Function to count the number of
// sub-matrices with all 1s
static int matrixAllOne(Boolean [,]arr)
{
// Array to store required prefix count of
// 1s from right to left for boolean array
int [,]p_arr = new int[n, n];
findPrefixCount(p_arr, arr);
// variable to store the final answer
int ans = 0;
/* Loop to evaluate each column of
the prefix matrix uniquely.
For each index of a column we will try to
determine the number of sub-matrices
starting from that index
and has all 1s */
for (int j = 0; j < n; j++)
{
int i = n - 1;
/* Stack to store elements and the count
of the numbers they popped
First part of pair will be the
value of inserted element.
Second part will be the count
of the number of elements pushed
before with a greater value */
Stack<pair> q = new Stack<pair>();
// variable to store the number of
// submatrices with all 1s
int to_sum = 0;
while (i >= 0)
{
int c = 0;
while (q.Count != 0 &&
q.Peek().first > p_arr[i, j])
{
to_sum -= (q.Peek().second + 1) *
(q.Peek().first - p_arr[i, j]);
c += q.Peek().second + 1;
q.Pop();
}
to_sum += p_arr[i, j];
ans += to_sum;
q.Push(new pair(p_arr[i, j], c));
i--;
}
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
Boolean [,]arr = {{ true, true, false },
{ true, false, true },
{ false, true, true }};
Console.WriteLine(matrixAllOne(arr));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to count number of
// sub-matrices with all 1s
var n = 3;
// Function to find required prefix-count for
// each row from right to left
function findPrefixCount(p_arr, arr)
{
for (var i = 0; i < n; i++) {
for (var j = n - 1; j >= 0; j--) {
if (!arr[i][j])
continue;
if (j != n - 1)
p_arr[i][j] += p_arr[i][j + 1];
p_arr[i][j] += arr[i][j];
}
}
}
// Function to count the number of
// sub-matrices with all 1s
function matrixAllOne(arr)
{
// Array to store required prefix count of
// 1s from right to left for boolean array
var p_arr = Array.from(Array(n), ()=>Array(n).fill(0));
findPrefixCount(p_arr, arr);
// variable to store the final answer
var ans = 0;
/* Loop to evaluate each column of
the prefix matrix uniquely.
For each index of a column we will try to
determine the number of sub-matrices
starting from that index
and has all 1s */
for (var j = 0; j < n; j++) {
var i = n - 1;
/* Stack to store elements and the count
of the numbers they popped
First part of pair will be the
value of inserted element.
Second part will be the count
of the number of elements pushed
before with a greater value */
var q = [];
// variable to store the number of
// submatrices with all 1s
var to_sum = 0;
while (i >= 0) {
var c = 0;
while (q.length != 0 && q[q.length-1][0] > p_arr[i][j]) {
to_sum -= (q[q.length-1][1] + 1) *
(q[q.length-1][0] - p_arr[i][j]);
c += q[q.length-1][1] + 1;
q.pop();
}
to_sum += p_arr[i][j];
ans += to_sum;
q.push([ p_arr[i][j], c ]);
i--;
}
}
return ans;
}
// Driver Code
var arr = [ [ 1, 1, 0 ],
[ 1, 0, 1 ],
[ 0, 1, 1 ] ];
document.write( matrixAllOne(arr));
</script>
Producción:
10
Complejidad de Tiempo : O(N 2 )
Espacio Auxiliar: O(N 2 ), ya que se ha tomado N 2 espacio extra.
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA