Contar ceros en una array ordenada por filas y columnas

Dada una array binaria N x N (los elementos en la array pueden ser 1 o 0) donde cada fila y columna de la array se ordena en orden ascendente, cuente el número de 0 presentes en ella.
La complejidad de tiempo esperada es O(N).

Ejemplos: 

Input: 
[0, 0, 0, 0, 1]
[0, 0, 0, 1, 1]
[0, 1, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 1, 1, 1, 1]

Output: 8


Input: 
[0, 0]
[0, 0]

Output: 4


Input: 
[1, 1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]

Output: 0

La idea es muy simple. Comenzamos desde la esquina inferior izquierda de la array y repetimos los pasos a continuación hasta que encontremos el borde superior o derecho de la array.

1. Disminuya el índice de la fila hasta que encontremos un 0. 
2. Agregue el número de 0 en la columna actual, es decir, el índice de fila actual + 1 al resultado y muévase a la derecha a la siguiente columna (Incremente el índice de columna en 1).

La lógica anterior funcionará ya que la array está ordenada por filas y columnas. La lógica también funcionará para cualquier array que contenga números enteros no negativos.

A continuación se muestra la implementación de la idea anterior:

// C++ program to count number of 0s in the given
// row-wise and column-wise sorted binary matrix.
#include <iostream>
using namespace std;
// define size of square matrix
#define N 5
 
// Function to count number of 0s in the given
// row-wise and column-wise sorted binary matrix.
int countZeroes(int mat[N][N])
{
    // start from bottom-left corner of the matrix
    int row = N - 1, col = 0;
 
    // stores number of zeroes in the matrix
    int count = 0;
 
    while (col < N)
    {
        // move up until you find a 0
        while (mat[row][col])
 
            // if zero is not found in current column,
            // we are done
            if (--row < 0)
                return count;
 
        // add 0s present in current column to result
        count += (row + 1);
 
        // move right to next column
        col++;
    }
 
    return count;
}
 
// Driver Program to test above functions
int main()
{
    int mat[N][N] =
    {
        { 0, 0, 0, 0, 1 },
        { 0, 0, 0, 1, 1 },
        { 0, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1 }
    };
 
    cout << countZeroes(mat);
 
    return 0;
}

// C program to count number of 0s in the given
// row-wise and column-wise sorted binary matrix.
#include <stdio.h>
 
// define size of square matrix
#define N 5
 
// Function to count number of 0s in the given
// row-wise and column-wise sorted binary matrix.
int countZeroes(int mat[N][N])
{
    // start from bottom-left corner of the matrix
    int row = N - 1, col = 0;
 
    // stores number of zeroes in the matrix
    int count = 0;
 
    while (col < N)
    {
        // move up until you find a 0
        while (mat[row][col])
 
            // if zero is not found in current column,
            // we are done
            if (--row < 0)
                return count;
 
        // add 0s present in current column to result
        count += (row + 1);
 
        // move right to next column
        col++;
    }
 
    return count;
}
 
// Driver Program to test above functions
int main()
{
    int mat[N][N] =
    {
        { 0, 0, 0, 0, 1 },
        { 0, 0, 0, 1, 1 },
        { 0, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1 }
    };
     
    printf("%d",countZeroes(mat));
 
    return 0;
}
 
// This code is contributed by kothavvsaakash.

// Java program to count number of 0s in the given
// row-wise and column-wise sorted binary matrix
import java.io.*;
 
class GFG
{
    public static int N = 5;
     
    // Function to count number of 0s in the given
    // row-wise and column-wise sorted binary matrix.
    static int countZeroes(int mat[][])
    {
        // start from bottom-left corner of the matrix
        int row = N - 1, col = 0;
  
        // stores number of zeroes in the matrix
        int count = 0;
  
        while (col < N)
        {
            // move up until you find a 0
            while (mat[row][col] > 0)
  
                // if zero is not found in current column,
                // we are done
                if (--row < 0)
                    return count;
  
            // add 0s present in current column to result
            count += (row + 1);
  
            // move right to next column
            col++;
        }
  
        return count;
    }
     
    // Driver program
    public static void main (String[] args)
    {
        int mat[][] = { { 0, 0, 0, 0, 1 },
                        { 0, 0, 0, 1, 1 },
                        { 0, 1, 1, 1, 1 },
                        { 1, 1, 1, 1, 1 },
                        { 1, 1, 1, 1, 1 } };
        System.out.println(countZeroes(mat));
    }
}
 
// This code is contributed by Pramod Kumar

# Python program to count number
# of 0s in the given row-wise
# and column-wise sorted
# binary matrix.
 
# Function to count number
# of 0s in the given
# row-wise and column-wise
# sorted binary matrix.
def countZeroes(mat):
     
    # start from bottom-left
    # corner of the matrix
    N = 5;
    row = N - 1;
    col = 0;
 
    # stores number of
    # zeroes in the matrix
    count = 0;
 
    while (col < N):
         
        # move up until
        # you find a 0
        while (mat[row][col]):
             
            # if zero is not found
            # in current column, we
            # are done
            if (row < 0):
                return count;
            row = row - 1;
 
        # add 0s present in
        # current column to result
        count = count + (row + 1);
 
        # move right to
        # next column
        col = col + 1;
 
    return count;
     
# Driver Code
mat = [[0, 0, 0, 0, 1],
       [0, 0, 0, 1, 1],
       [0, 1, 1, 1, 1],
       [1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1]];
 
print( countZeroes(mat));
 
# This code is contributed
# by chandan_jnu

// C# program to count number of
// 0s in the given row-wise and
// column-wise sorted binary matrix
using System;
 
class GFG
{
    public static int N = 5;
     
    // Function to count number of
    // 0s in the given row-wise and
    // column-wise sorted binary matrix.
    static int countZeroes(int [,] mat)
    {
        // start from bottom-left
        // corner of the matrix
        int row = N - 1, col = 0;
 
        // stores number of zeroes
        // in the matrix
        int count = 0;
 
        while (col < N)
        {
            // move up until you find a 0
            while (mat[row,col] > 0)
 
                // if zero is not found in
                // current column,
                // we are done
                if (--row < 0)
                    return count;
 
            // add 0s present in current
            // column to result
            count += (row + 1);
 
            // move right to next column
            col++;
        }
 
        return count;
    }
     
    // Driver Code
    public static void Main ()
    {
        int [,] mat = { { 0, 0, 0, 0, 1 },
                        { 0, 0, 0, 1, 1 },
                        { 0, 1, 1, 1, 1 },
                        { 1, 1, 1, 1, 1 },
                        { 1, 1, 1, 1, 1 } };
        Console.WriteLine(countZeroes(mat));
    }
}
 
// This code is contributed by KRV.

<?php
// PHP program to count number
// of 0s in the given row-wise
// and column-wise sorted
// binary matrix.
 
// Function to count number
// of 0s in the given
// row-wise and column-wise
// sorted binary matrix.
function countZeroes($mat)
{
    // start from bottom-left
    // corner of the matrix
    $N = 5;
    $row = $N - 1;
    $col = 0;
 
    // stores number of
    // zeroes in the matrix
    $count = 0;
 
    while ($col < $N)
    {
        // move up until
        // you find a 0
        while ($mat[$row][$col])
 
            // if zero is not found
            // in current column, we
            // are done
            if (--$row < 0)
                return $count;
 
        // add 0s present in
        // current column to result
        $count += ($row + 1);
 
        // move right to
        // next column
        $col++;
    }
 
    return $count;
}
 
// Driver Code
$mat = array(array(0, 0, 0, 0, 1),
             array(0, 0, 0, 1, 1),
             array(0, 1, 1, 1, 1),
             array(1, 1, 1, 1, 1),
             array(1, 1, 1, 1, 1));
 
echo countZeroes($mat);
 
// This code is contributed by Sam007
?>

<script>
 
// JavaScript program to count number of 0s in the given
// row-wise and column-wise sorted binary matrix
 
    let N = 5;
       
    // Function to count number of 0s in the given
    // row-wise and column-wise sorted binary matrix.
    function countZeroes(mat)
    {
        // start from bottom-left corner of the matrix
        let row = N - 1, col = 0;
    
        // stores number of zeroes in the matrix
        let count = 0;
    
        while (col < N)
        {
            // move up until you find a 0
            while (mat[row][col] > 0)
    
                // if zero is not found in current column,
                // we are done
                if (--row < 0)
                    return count;
    
            // add 0s present in current column to result
            count += (row + 1);
    
            // move right to next column
            col++;
        }
    
        return count;
    }
 
 
    // Driver code
 
        let mat = [[ 0, 0, 0, 0, 1 ],
                        [ 0, 0, 0, 1, 1 ],
                        [ 0, 1, 1, 1, 1 ],
                        [ 1, 1, 1, 1, 1 ],
                        [ 1, 1, 1, 1, 1 ]];
        document.write(countZeroes(mat));
 
</script>

8

La complejidad temporal de la solución anterior es O(n) ya que la solución sigue un camino único desde la esquina inferior izquierda hasta el borde superior o derecho de la array. 
El espacio auxiliar utilizado por el programa es O(1).

Este artículo es una contribución de Aditya Goel . 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. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.