Set Matrix Zeroes

Q: Qual é a complexidade de tempo de Set Matrix Zeroes?

O(m·n) para uma matriz m × n , já que cada célula é lida e escrita um número constante de vezes. Nenhuma solução é mais eficiente, pois qualquer célula ignorada poderia ser o 0 que muda a resposta. O espaço extra é O(m + n) com arrays marcadores e O(1) usando a primeira linha e a primeira coluna como marcadores.

MédioArrays e strings Hashing

+10

A entrada é uma grade m × n de inteiros, fornecida linha por linha, de modo que matrix[i][j] fica na linha i e na coluna j. Sempre que a grade contiver um 0, defina toda essa linha e toda essa coluna como 0. Conte apenas os zeros presentes no início: uma célula que você transforma em 0 não zera sua própria linha nem sua própria coluna. Você pode alterar a grade in-place; retorne-a.

Função

setZeroes(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: a grade de números inteiros, uma lista interna por linha
Retornainteger-2d-array: a matriz com todas as linhas e colunas que continham um 0 definidas como 0

Restrições

m == matrix.length e n == matrix[i].length
1 ≤ m, n ≤ 1000 e m × n ≤ 5000
Todos os m linhas contêm n valores.
-1000 ≤ matrix[i][j] ≤ 1000

Exemplos

Entrada: matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
Saída: [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
Explicação: O único 0 está na linha 1, coluna 1. A linha 1 fica toda zerada, e o mesmo acontece com a coluna 1, que transforma o 8 e o 6 em 0. Os quatro cantos não estão em nenhuma das linhas e mantêm seus valores.

Para ir além

A melhor abordagem abaixo mantém dois booleanos extras. Você consegue se virar com apenas um, deixando matrix[0][0] representar a primeira linha?

Solução

Um 0 que você escreve é exatamente igual a um 0 que já estava lá, então zerar linhas durante a varredura espalha zeros pela matriz. Separe a leitura da escrita: primeiro registre quais linhas e colunas continham um 0 e, em seguida, zere-as. Mantenha esse registro em dois arrays ou, para usar espaço extra O(1), na primeira linha e na primeira coluna da própria matriz.

Marque linhas e colunas em dois arrays

Intuição

Uma célula termina com 0 exatamente quando sua linha ou sua coluna continha um 0 no início. Portanto, registre duas listas de informações, zeroRow[i] e zeroCol[j], em uma passagem que não faz nenhuma gravação e, em seguida, limpe cada célula cuja linha ou coluna esteja marcada. Nada se propaga, pois todas as leituras são feitas antes da primeira gravação.

Cada passagem visita as m·n células uma vez, então o tempo é O(m·n), e os arrays armazenam m + n valores booleanos.

Algoritmo

Crie zeroRow com m entradas e zeroCol com n entradas, todas falsas.
Percorra cada célula. Quando matrix[i][j] for 0, defina zeroRow[i] e zeroCol[j] como true.
Percorra cada célula novamente e defina-a como 0 quando zeroRow[i] ou zeroCol[j] for true.
Retorne a matriz.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    zero_row = [False] * m
    zero_col = [False] * n
    # Pass 1: only read, so a new zero can never spread further.
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                zero_row[i] = True
                zero_col[j] = True
    # Pass 2: write.
    for i in range(m):
        for j in range(n):
            if zero_row[i] or zero_col[j]:
                matrix[i][j] = 0
    return matrix

Use a primeira linha e a primeira coluna como marcadores

Intuição

A primeira coluna tem uma célula por linha e a primeira linha, uma por coluna, correspondendo às formas dos dois arrays de marcadores. Assim, um 0 na linha i, coluna j, grava 0 em matrix[i][0] e matrix[0][j]. Isso não perde nada: cada uma dessas células está em uma linha que precisa se tornar 0 de qualquer forma.

A linha 0 e a coluna 0 são dados e também marcadores, e um marcador ali oculta se elas continham um 0 próprio. Portanto, verifique-as primeiro e guarde as respostas em dois booleanos. Marque e preencha apenas as células com i ≥ 1 e j ≥ 1, e limpe a linha 0 e a coluna 0 por último, pois o preenchimento lê esses valores.

No segundo exemplo, o 3 na linha 1, coluna 1, permanece porque seus marcadores, matrix[1][0] = 9 e matrix[0][1] = 4, não são 0. O tempo continua sendo O(m·n), com dois booleanos de memória extra (O(m·n) em R, que copia a entrada primeiro).

Algoritmo

Defina firstRowZero se a linha 0 contiver um 0 e firstColZero se a coluna 0 contiver um 0.
Para cada célula com i ≥ 1 e j ≥ 1 que contenha 0, defina matrix[i][0] e matrix[0][j] como 0.
Para cada célula com i ≥ 1 e j ≥ 1, defina-a como 0 quando matrix[i][0] ou matrix[0][j] for 0.
Se firstRowZero for verdadeiro, defina a linha 0 como 0. Se firstColZero for verdadeiro, defina a coluna 0 como 0.
Retorne a matriz.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    # The first row and column will hold the markers, so remember first
    # whether they need to become zero themselves.
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))
    # Mark: a zero inside the matrix flags its row in column 0
    # and its column in row 0.
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    # Fill the inside from the markers.
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    # The marker row and column go last.
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0
    return matrix

Armadilhas e casos extremos

Limpar uma linha e uma coluna assim que encontrar um 0. No primeiro exemplo, o novo 0 na linha 1, coluna 2 limpa então a coluna 2, e apenas o 3 no canto superior esquerdo permanece.
Deixar matrix[0][0] marcar tanto a linha 0 quanto a coluna 0. Em [[1, 2, 3], [0, 5, 6], [7, 8, 9]], o 0 na coluna 0 limpa então incorretamente a linha 0.
Limpar a linha 0 ou a coluna 0 antes de preencher. Em [[0, 2, 3], [4, 5, 6], [7, 8, 9]], todas as colunas parecem então marcadas, e a matriz inteira se torna 0.
Esquecer linhas únicas. Com uma linha, os loops que começam em 1 não fazem nada, e os booleanos fazem todo o trabalho: [[1, 0, 3]] deve se tornar [[0, 0, 0]].

Perguntas frequentes3

Por que você não pode definir os zeros enquanto percorre a matriz?

Um 0 que você escreve tem a mesma aparência que um 0 original. Quando a varredura chega até ele, ela limpa a própria linha e coluna, e esses novos zeros se espalham ainda mais. Registre cada zero original antes de alterar qualquer célula.

Qual é a complexidade de tempo de Set Matrix Zeroes?

O(m·n) para uma matriz m × n, já que cada célula é lida e escrita um número constante de vezes. Nenhuma solução é mais eficiente, pois qualquer célula ignorada poderia ser o 0 que muda a resposta. O espaço extra é O(m + n) com arrays marcadores e O(1) usando a primeira linha e a primeira coluna como marcadores.

Você pode marcar as células com um valor especial em vez de 0?

Algumas soluções escrevem um marcador nas células que devem ser limpas e transformam os marcadores em zeros no final. Isso só funciona se o marcador nunca puder aparecer na entrada, algo que uma matriz de inteiros raramente garante. Escrevê-lo ao longo de uma linha e de uma coluna para cada 0 também custa O(m·n·(m + n)) de tempo.

def setZeroes(matrix):
    # Escreva o código aqui

Teste #1

Teste #2

Argumento

matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]

Saída Esperada

[[3, 0, 1], [0, 0, 0], [2, 0, 4]]