Mismo valor en cada diagonal
La misión
Problema
Un patrón de prueba para una pantalla se guarda como una cuadrícula de números. Es válido solo si cada diagonal que va de arriba a la izquierda hacia abajo a la derecha contiene un único valor repetido. Dada la cuadrícula, devuelve True si es válida y False si no lo es. La cuadrícula tiene entre 1 y 20 filas y entre 1 y 20 columnas, y cada valor está entre 0 y 99.
Ejemplos
Input: grid = [[1, 2, 3, 4], [5, 1, 2, 3], [9, 5, 1, 2]]
Output: True
Por qué: las diagonales son [9], [5, 5], [1, 1, 1], [2, 2, 2], [3, 3] y [4]
Input: grid = [[1, 2], [2, 2]]
Output: False
Por qué: la diagonal principal tiene un 1 y luego un 2
Input: grid = [[7]]
Output: True
Por qué: caso límite: una sola celda es una diagonal con un solo valor
Pistas
0 / 3
Dos celdas están en la misma diagonal de arriba a la izquierda hacia abajo a la derecha exactamente cuando su fila menos su columna da lo mismo.
No necesitas reunir diagonales enteras. Basta con que cada celda coincida con la celda que está justo arriba y a su izquierda, porque así la igualdad se encadena a lo largo de la diagonal.
Recorre cada celda que tenga un vecino arriba a la izquierda, es decir, toda celda fuera de la primera fila y de la primera columna, y devuelve False en la primera discrepancia.
- Tiempo objetivo
- O(rows · cols)
- Espacio objetivo
- O(1)
Restricciones
- 1 ≤ rows ≤ 20
- 1 ≤ cols ≤ 20
- 0 ≤ value ≤ 99
Solución
Bajar un paso y moverse un paso a la derecha deja igual la fila menos la columna, así que el predecesor diagonal de cada celda es la celda en fila - 1, columna - 1. Si cada celda es igual a ese predecesor, la igualdad se encadena desde la primera celda de cada diagonal hasta la última, así que toda la diagonal tiene un solo valor; una sola discrepancia la rompe. Comparar cada celda con su vecino no necesita almacenamiento extra, y la misma comprobación funciona si las filas llegan una por una, ya que cada fila nueva solo tiene que coincidir con la anterior desplazada una posición a la derecha. El tiempo es O(rows × cols) y el espacio es O(1).
def diagonal_constant(grid):
for r in range(1, len(grid)):
for c in range(1, len(grid[0])):
if grid[r][c] != grid[r - 1][c - 1]: # up-left neighbour differs
return False
return True
print(diagonal_constant([[1, 2, 3, 4], [5, 1, 2, 3], [9, 5, 1, 2]])) # -> True
print(diagonal_constant([[1, 2], [2, 2]])) # -> False
print(diagonal_constant([[7]])) # -> True¿Lo que te frena es la idea y no el código? Rotar in-place lo explica.