Columna más a la izquierda con al menos un 1 en una array binaria ordenada por filas | conjunto 2

Dada una array binaria mat[][] que contiene ceros y unos. Cada fila de la array se ordena en orden no decreciente, la tarea es encontrar la columna más a la izquierda de la array con al menos un 1 en ella.
Nota: Si no existe tal columna, devuelva -1. 
Ejemplos: 
 

Input: 
mat[][] = {{0, 0, 0, 1}
           {0, 1, 1, 1}
           {0, 0, 1, 1}}
Output: 2
Explanation:
The 2nd column of the
matrix contains atleast a 1.

Input: 
mat[][] = {{0, 0, 0}
           {0, 1, 1}  
           {1, 1, 1}}
Output: 1
Explanation:
The 1st column of the
matrix contains atleast a 1.

Input: 
mat[][] = {{0, 0}
           {0, 0}}
Output: -1
Explanation:
There is no such column which 
contains atleast one 1.

Acercarse: 
 

• Aquí comenzamos nuestro recorrido desde el último elemento de la primera fila. Esto incluye dos pasos. 
  1. Si el elemento de iteración actual es 1, decrementamos el índice de la columna. Como encontramos el índice de la columna más a la izquierda con el valor 1, no tenemos que verificar los elementos con un índice de columna mayor. 
  2. Si el elemento de iteración actual es 0, incrementamos el índice de fila. Como ese elemento es 0, no necesitamos verificar los elementos anteriores de esa fila. 
• Continuamos hasta que uno de los índices de fila o columna deje de ser válido. 
   

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

// C++ program to calculate leftmost
// column having at least a 1
#include <bits/stdc++.h>
using namespace std;
 
#define N 3
#define M 4
 
// Function return leftmost
// column having at least a 1
int FindColumn(int mat[N][M])
{
    int row = 0, col = M - 1;
    int flag = 0;
 
    while (row < N && col >= 0)
    {
        // If current element is
        // 1 decrement column by 1
        if (mat[row][col] == 1)
        {
            col--;
            flag = 1;
        }
        // If current element is
        // 0 increment row by 1
        else
        {
            row++;
        }
    }
 
    col++;
     
    if (flag)
        return col + 1;
    else
        return -1;
}
 
// Driver code
int main()
{
    int mat[N][M] = { { 0, 0, 0, 1 },
                      { 0, 1, 1, 1 },
                      { 0, 0, 1, 1 } };
 
    cout << FindColumn(mat);
 
    return 0;
}

// Java program to calculate leftmost
// column having at least a 1
import java.util.*;
 
class GFG{
 
static final int N = 3;
static final int M = 4;
 
// Function return leftmost
// column having at least a 1
static int FindColumn(int mat[][])
{
    int row = 0, col = M - 1;
    int flag = 0;
 
    while(row < N && col >= 0)
    {
        // If current element is
        // 1 decrement column by 1
        if(mat[row][col] == 1)
        {
           col--;
           flag = 1;
        }
        // If current element is
        // 0 increment row by 1
        else
        {
            row++;
        }
    }
    col++;
 
    if (flag!=0)
        return col + 1;
    else
        return -1;
}
 
// Driver code
public static void main(String[] args)
{
    int[][] mat = { { 0, 0, 0, 1 },
                    { 0, 1, 1, 1 },
                    { 0, 0, 1, 1 } };
                     
    System.out.print(FindColumn(mat));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to calculate leftmost
# column having at least a 1
N = 3
M = 4
 
# Function return leftmost
# column having at least a 1
def findColumn(mat: list) -> int:
    row = 0
    col = M - 1
 
    while row < N and col >= 0:
 
        # If current element is
        # 1 decrement column by 1
        if mat[row][col] == 1:
            col -= 1
            flag = 1
 
        # If current element is
        # 0 increment row by 1
        else:
            row += 1
             
    col += 1
 
    if flag:
        return col + 1
    else:
        return -1
 
# Driver Code
if __name__ == "__main__":
     
    mat = [ [0, 0, 0, 1],
            [0, 1, 1, 1],
            [0, 0, 1, 1] ]
               
    print(findColumn(mat))
 
# This code is contributed by sanjeev2552

// C# program to calculate leftmost
// column having at least 1
using System;
 
class GFG{
 
static readonly int N = 3;
static readonly int M = 4;
 
// Function return leftmost
// column having at least a 1
static int FindColumn(int [,]mat)
{
    int row = 0, col = M - 1;
    int flag = 0;
 
    while(row < N && col >= 0)
    {
         
        // If current element is
        // 1 decrement column by 1
        if (mat[row, col] == 1)
        {
            col--;
            flag = 1;
        }
         
        // If current element is
        // 0 increment row by 1
        else
        {
            row++;
        }
    }
    col++;
 
    if (flag != 0)
        return col + 1;
    else
        return -1;
}
 
// Driver code
public static void Main(String[] args)
{
    int[,] mat = { { 0, 0, 0, 1 },
                   { 0, 1, 1, 1 },
                   { 0, 0, 1, 1 } };
                     
    Console.Write(FindColumn(mat));
}
}
 
// This code is contributed by Rohit_ranjan

<script>
 
    // JavaScript program to calculate leftmost
    // column having at least 1
     
    let N = 3;
    let M = 4;
 
    // Function return leftmost
    // column having at least a 1
    function FindColumn(mat)
    {
        let row = 0, col = M - 1;
        let flag = 0;
 
        while(row < N && col >= 0)
        {
 
            // If current element is
            // 1 decrement column by 1
            if (mat[row][col] == 1)
            {
                col--;
                flag = 1;
            }
 
            // If current element is
            // 0 increment row by 1
            else
            {
                row++;
            }
        }
        col++;
 
        if (flag != 0)
            return col + 1;
        else
            return -1;
    }
     
    let mat = [ [ 0, 0, 0, 1 ],
                 [ 0, 1, 1, 1 ],
                 [ 0, 0, 1, 1 ] ];
                       
    document.write(FindColumn(mat));
 
</script>

2

Complejidad Temporal: O(N + M). donde N es el número de fila y M es el número de columna. 
Complejidad espacial: O(1)