Número de subarrays con valor OR 1

Dada una array binaria N*N , la tarea es encontrar el número de subarrays rectangulares con OR valor 1.

Ejemplos:  

Input : arr[][] = {{0, 0, 0},
                   {0, 0, 0},
                   {0, 0, 0}}
Output : 0
Explanation: All the submatrices will have an OR value 0.
Thus, ans = 0.

Input : arr[][] = {{0, 0, 0},
                  {0, 1, 0},
                  {0, 0, 0}}
Output : 16 

Una solución simple será generar todas las subarrays posibles y luego verificar si alguno de los valores dentro de ellas es 1. Si para una subarray, al menos un solo elemento es uno, incrementamos el valor de la respuesta final para una. La complejidad temporal del enfoque anterior es O(n ⁶ ).

Mejor enfoque : echemos un vistazo a este problema de otra manera. Ahora intentaremos encontrar el número de subarrays con todos 0. Y para la respuesta final, restaremos este valor del número total de subarrays.
Para optimizar el proceso, para cada índice de la array, intentaremos encontrar el número de subarrays a partir de ese índice que tengan todos ceros.
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 0, entonces en p_arr[R][C], almacenaremos el número de 0 a la derecha de la celda (R, C) a lo largo de la fila ‘R’ antes de que encontremos ‘1’ o el final de la array más uno.
• Si arr[R][C] es igual a 1, p_arr[R][C] es igual a cero.

Para crear esta array, utilizaremos la siguiente relación de recurrencia.  

IF arr[R][C] is 0
    p_arr[R][C] = p_arr[R][C+1] + 1
ELSE 
    p_arr[R][C] = 0

arr[][] = {{1, 0, 0, 0},
           {0, 1, 0, 1},
           {0, 1, 0, 0},
           {0, 0, 0, 0}}

p_arr[][] for above will look like
          {{0, 3, 2, 1},
           {1, 0, 1, 0},
           {1, 0, 2, 1},
           {4, 3, 2, 1}}

Una vez que tengamos la array p_arr requerida , comenzaremos a procesar 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 0.
Para esto, podemos usar la estructura de datos de la pila.

Algoritmo :  

1. 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 la pila con un valor estrictamente mayor que el valor del elemento actual. Usaremos pares 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 0 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 0 en cada paso.
2. 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, j}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.
3. Actualizamos el número de subarrays con todos ceros como count_zero_subarrays += to_sum.
4. Finalmente, empujamos ese elemento en la pila después de emparejarlo con C _{i, j} .

El número total de subarrays en una array N*N es igual a: 

(N2 * (N + 1)2)/4

Así, la respuesta final será: 

ans = (N2 * (N + 1)2)/4 - count_zero_submatrices 

Creamos la array de prefijos en O(N ² ) 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 ² ).

A continuación se muestra la implementación del enfoque anterior: 

// C++ program to count number of submatrices
// with OR value 1
 
#include <iostream>
#include <stack>
#define n 3
using namespace std;
 
// 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 find the count of submatrices
// with OR value 1
int matrixOrValueOne(bool arr[][n])
{
    // Array to store prefix count of zeros from
    // right to left for boolean array
    int p_arr[n][n] = { 0 };
 
    findPrefixCount(p_arr, arr);
 
    // Variable to store the count of
    // submatrices with OR value 0
    int count_zero_submatrices = 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 0s
        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];
 
            count_zero_submatrices += to_sum;
 
            q.push({ p_arr[i][j], c });
 
            i--;
        }
    }
 
    // Return the final answer
    return (n * (n + 1) * n * (n + 1)) / 4
           - count_zero_submatrices;
}
 
// Driver Code
int main()
{
    bool arr[][n] = { { 0, 0, 0 },
                      { 0, 1, 0 },
                      { 0, 0, 0 } };
 
    cout << matrixOrValueOne(arr);
 
    return 0;
}

// Java program to count number of submatrices
// with OR value 1
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] == false ? 1 : 0);
        }
}
 
// Function to find the count of submatrices
// with OR value 1
static int matrixOrValueOne(boolean arr[][])
{
    // Array to store prefix count of zeros from
    // right to left for boolean array
    int [][]p_arr = new int[n][n];
 
    findPrefixCount(p_arr, arr);
 
    // Variable to store the count of
    // submatrices with OR value 0
    int count_zero_submatrices = 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 0s
        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];
 
            count_zero_submatrices += to_sum;
 
            q.add(new pair(p_arr[i][j], c ));
 
            i--;
        }
    }
 
    // Return the final answer
    return (n * (n + 1) * n * (n + 1)) / 4
        - count_zero_submatrices;
}
 
// Driver Code
public static void main(String[] args)
{
    boolean arr[][] = { { false, false, false },
                        { false, true, false },
                        { false, false, false } };
 
    System.out.println(matrixOrValueOne(arr));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 program to count number
# of submatrices with OR value 1
 
# 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 arr[i][j]:
                continue
            if j != n - 1:
                p_arr[i][j] += p_arr[i][j + 1]
 
            p_arr[i][j] += int(not arr[i][j])
 
# Function to find the count
# of submatrices with OR value 1
def matrixOrValueOne(arr):
 
    # Array to store prefix count of zeros
    # 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 count of
    # submatrices with OR value 0
    count_zero_submatrices = 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 0s
        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.pop()[1] + 1
 
            to_sum += p_arr[i][j]
            count_zero_submatrices += to_sum
 
            q.append((p_arr[i][j], c))
            i -= 1
 
    # Return the final answer
    return ((n * (n + 1) * n * (n + 1)) //
             4 - count_zero_submatrices)
 
# Driver Code
if __name__ == "__main__":
 
    n = 3
    arr = [[0, 0, 0],
           [0, 1, 0],
           [0, 0, 0]]
 
    print(matrixOrValueOne(arr))
 
# This code is contributed by Rituraj Jain

// C# program to count number of submatrices
// with OR value 1
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,
                            bool [,]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] == false ? 1 : 0);
        }
}
 
// Function to find the count of submatrices
// with OR value 1
static int matrixOrValueOne(bool [,]arr)
{
    // Array to store prefix count of zeros from
    // right to left for bool array
    int [,]p_arr = new int[n, n];
 
    findPrefixCount(p_arr, arr);
 
    // Variable to store the count of
    // submatrices with OR value 0
    int count_zero_submatrices = 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 0s
        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];
 
            count_zero_submatrices += to_sum;
 
            q.Push(new pair(p_arr[i, j], c));
 
            i--;
        }
    }
 
    // Return the final answer
    return (n * (n + 1) * n * (n + 1)) / 4 -
                     count_zero_submatrices;
}
 
// Driver Code
public static void Main(String[] args)
{
    bool [,]arr = { { false, false, false },
                    { false, true, false },
                    { false, false, false } };
 
    Console.WriteLine(matrixOrValueOne(arr));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript program to count number of submatrices
// with OR value 1
 
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 find the count of submatrices
// with OR value 1
function matrixOrValueOne(arr)
{
    // Array to store prefix count of zeros 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 count of
    // submatrices with OR value 0
    var count_zero_submatrices = 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 0s
        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];
 
            count_zero_submatrices += to_sum;
 
            q.push([p_arr[i][j], c]);
 
            i--;
        }
    }
 
    // Return the final answer
    return (n * (n + 1) * n * (n + 1)) / 4
           - count_zero_submatrices;
}
 
// Driver Code
var arr = [ [ 0, 0, 0 ],
                  [ 0, 1, 0 ],
                  [ 0, 0, 0 ] ];
document.write( matrixOrValueOne(arr));
 
</script>

16

Complejidad temporal: O(n ² )

Espacio Auxiliar: O(n ² )