Spiral Matrix

MedioMatemáticas y simulación Arrays y cadenas

+10

Recibes una matriz de enteros con m filas y n columnas, representada como una lista de filas. Devuelve todos sus valores en orden espiral.

Empieza en la esquina superior izquierda y avanza hacia la derecha por la fila superior; después, baja por la columna derecha, avanza hacia la izquierda por la fila inferior y sube por la columna izquierda. Sigue dando vueltas hacia el interior en sentido horario hasta haber leído cada valor exactamente una vez.

Función

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

matrixinteger-2d-array: la cuadrícula de enteros, como una lista de filas de igual longitud
Devuelveinteger-array: cada valor de la matriz en orden espiral en el sentido de las agujas del reloj, comenzando en la esquina superior izquierda

Restricciones

1 ≤ m, n ≤ 80, donde m = matrix.length y n = matrix[i].length
Cada fila tiene la misma longitud n.
-100 ≤ matrix[i][j] ≤ 100

Ejemplos

Entrada: matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]
Salida: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Explicación: Los valores aumentan a lo largo de la espiral. El anillo exterior se lee como 1, 2, 3 en la parte superior, 4, 5, 6 hacia abajo por la derecha, 7, 8 de vuelta por la parte inferior y 9, 10 hacia arriba por la izquierda. La capa interior es una sola columna, que se lee una vez de arriba abajo: 11, 12.

Entrada: matrix = [[7, 1, 5, 3], [2, 9, -4, 6], [8, 0, 4, -1]]
Salida: [7, 1, 5, 3, 6, -1, 4, 0, 8, 2, 9, -4]
Explicación: El anillo exterior da 7, 1, 5, 3, después 6, -1 bajando por el lado derecho, 4, 0, 8 de vuelta por la parte inferior y 2 subiendo por el lado izquierdo. Lo que queda es la única fila 9, -4, leída una vez de izquierda a derecha.

+15 pruebas ocultas al enviar

Para ir más allá

¿Puedes devolver los valores en sentido antihorario, empezando por la esquina superior izquierda y bajando primero por la columna izquierda?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Aquí no hay matemáticas ingeniosas; el problema es llevar la cuenta, y es ahí donde fallan las soluciones. Hay que leer cada esquina una sola vez, no dos, y la capa más interna puede ser una sola fila o una sola columna, donde una vuelta completa pasaría otra vez por los mismos valores. Puedes recorrerla como un robot que gira a la derecha cuando encuentra un obstáculo y recuerda qué celdas ha leído. O puedes ir pelando la matriz anillo por anillo con cuatro límites que se reducen, lo que no requiere memoria adicional.

Avanza y gira a la derecha cuando haya un obstáculo

Intuición

Imagina a un caminante en la celda superior izquierda, mirando hacia la derecha. Lee la celda en la que está y después intenta avanzar. Si ese paso lo sacara de la matriz o lo llevara a una celda que ya ha leído, gira a la derecha (derecha, abajo, izquierda, arriba y luego otra vez a la derecha) y da el paso en esa dirección. Esa regla dibuja la espiral: los bordes de la matriz detienen la primera vuelta, y las celdas leídas hasta ese momento actúan como paredes para todas las vueltas posteriores.

Mantén la dirección como un índice d en dos arreglos pequeños, dr = [0, 1, 0, -1] y dc = [1, 0, -1, 0], de modo que un giro a la derecha sea d = (d+1) % 4. Mantén una cuadrícula booleana seen del mismo tamaño que la matriz. En el primer ejemplo, el caminante lee 1, 2, 3, llega al borde derecho y gira hacia abajo para leer 4, 5, 6, gira a la izquierda para leer 7, 8 y hacia arriba para leer 9, 10. Encima de 10 está el 1, que ya ha leído, así que gira a la derecha hacia 11. A la derecha de 11 está el 4, que ya ha leído, así que gira hacia abajo hasta 12.

Ejecuta el bucle exactamente m × n veces, una por celda, y nunca necesitarás detectar el final. Después de la última lectura, el caminante puede quedar mirando hacia una pared, pero no vuelve a dar ningún paso. Cada celda se lee una vez, así que el tiempo es O(m × n). La cuadrícula seen requiere O(m × n) de memoria adicional, que el siguiente enfoque elimina.

Algoritmo

Empieza en la fila 0, columna 0, mirando hacia la derecha, con una cuadrícula seen toda en false.
Repite m × n veces: añade el valor actual y marca su celda como vista.
Calcula la siguiente celda en la dirección actual. Si está fuera de la matriz o ya se ha visto, gira a la derecha y vuelve a calcularla.
Muévete a esa celda.
Devuelve los valores en el orden en que los añadiste.

def spiralOrder(matrix):
    rows, cols = len(matrix), len(matrix[0])
    seen = [[False] * cols for _ in range(rows)]
    # Directions in clockwise order: right, down, left, up.
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    r = c = d = 0
    result = []
    for _ in range(rows * cols):
        result.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + dr[d], c + dc[d]
        # Blocked by the edge or by a cell already read: turn right.
        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]
        r, c = nr, nc
    return result

Retira las capas con cuatro límites

Intuición

La espiral es un conjunto de anillos anidados. Describe el anillo actual con cuatro límites: filas de top a bottom, columnas de left a right. Una vuelta recorre la fila superior de left a right, la columna derecha de top+1 hacia abajo hasta bottom, la fila inferior de right-1 de vuelta a left y la columna izquierda de bottom-1 hacia arriba hasta top+1. Cada lado empieza una celda después del final del lado anterior, por lo que cada esquina se lee exactamente una vez. Después, mueve los cuatro límites un paso hacia adentro y repite mientras top ≤ bottom y left ≤ right.

La trampa es un anillo que tiene solo una fila o una columna de grosor, donde el recorrido de vuelta pasa por celdas ya leídas. En el segundo ejemplo, después del anillo exterior, los límites son top = bottom = 1, left = 1 y right = 2: la única fila 9, -4. La fila superior lee ambos valores y la columna derecha no tiene nada debajo de top. Pero la fila inferior es esa misma fila, y recorrerla de vuelta añadiría 9 por segunda vez. Por eso, recorre la fila inferior y la columna izquierda solo cuando top < bottom y left < right. El tercer ejemplo es el caso inverso: en la única columna 4, 1, 7, recorrer de vuelta hacia arriba la columna izquierda volvería a leer 1.

Cada valor se lee una vez, así que el tiempo es O(m × n), el mínimo posible, ya que la respuesta contiene todos los valores. Además de la respuesta, la memoria consta de cuatro enteros.

Algoritmo

Establece top = 0, bottom = m-1, left = 0, right = n-1.
Mientras top ≤ bottom y left ≤ right, lee la fila superior desde left hasta right y la columna derecha desde top+1 hasta bottom.
Si top < bottom y left < right, lee la fila inferior desde right-1 hasta left y la columna izquierda desde bottom-1 hasta top+1.
Suma uno a top y left, resta uno a bottom y right.
Devuelve los valores en el orden en que los leíste.

def spiralOrder(matrix):
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    result = []
    while top <= bottom and left <= right:
        # Top row, left to right, then right column, top to bottom.
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        for r in range(top + 1, bottom + 1):
            result.append(matrix[r][right])
        # A layer one row or one column thick has no way back:
        # walking back would read the same cells again.
        if top < bottom and left < right:
            # Bottom row, right to left, then left column, bottom to top.
            for c in range(right - 1, left - 1, -1):
                result.append(matrix[bottom][c])
            for r in range(bottom - 1, top, -1):
                result.append(matrix[r][left])
        # Step in to the next layer.
        top += 1
        bottom -= 1
        left += 1
        right -= 1
    return result

Errores comunes y casos límite

Los bucles son cortos, así que los errores aparecen en las esquinas y en la última capa.

Leer dos veces la última capa cuando tiene una fila o una columna. Sin la comprobación top < bottom y left < right, el segundo ejemplo termina en 9, -4, 9 y el tercero lee 4, 1, 7, 1.
Leer dos veces una esquina. Si cada lado va desde su propia primera celda hasta su propia última celda, dos lados leen cada esquina. Empieza cada lado una celda después de donde terminó el lado anterior.
Usar el bucle mientras top < bottom en lugar de top ≤ bottom. Esto se detiene antes del centro de un cuadrado impar: en una matriz de 3 × 3, nunca se lee el valor central.
Confundir filas y columnas en una matriz que no es cuadrada. Usar matrix.length para ambos límites funciona en todas las pruebas con matrices cuadradas y falla con una de 3 × 4.
Olvidar las entradas delgadas: una fila, una columna, una celda. Cada una es una sola capa que nunca llega a la fila inferior ni a la columna izquierda.
En R, a:b cuenta hacia atrás cuando a > b, así que un rango vacío como 3:2 da 3, 2 en lugar de nada; protégelo o usa seq_len. En Lua y R, las filas y las columnas empiezan en 1.

Preguntas frecuentes4

¿Cuál es la complejidad temporal y espacial de Spiral Matrix?

Ambos enfoques leen cada valor una vez, así que el tiempo es O(m × n), y ninguna solución puede hacerlo mejor porque la respuesta contiene todos los valores. Pelar capas con cuatro límites utiliza O(1) de memoria adicional, aparte de la respuesta. El recorrido que gira cuando encuentra un bloqueo utiliza una cuadrícula de O(m × n) para recordar qué celdas ha leído.

¿Cómo evitas leer un valor dos veces en un recorrido en espiral?

Hay dos lugares que provocan repeticiones. En las esquinas, empieza cada lado una celda después de donde terminó el lado anterior, para que cada esquina pertenezca a un solo lado. En la última capa, lee la fila inferior y la columna izquierda solo cuando la capa tenga más de una fila y más de una columna, ya que, de lo contrario, el recorrido de vuelta pasaría por celdas que ya has leído.

¿Cómo se llena una matriz en orden espiral en lugar de leer una?

Usa los mismos cuatro límites y los mismos cuatro lados, pero escribe en lugar de leer. Mantén un contador que empiece en 1 y guárdalo en cada celda a medida que avanzas, sumando uno cada vez. Para una matriz de n × n, el contador termina en n², y el primer ejemplo anterior es lo que se obtiene para una cuadrícula de 4 × 3.

¿Por qué girar a la derecha cuando hay un bloqueo produce una espiral?

En la primera vuelta, el recorrido gira en los cuatro bordes de la matriz. En cada vuelta posterior, las celdas leídas antes actúan como paredes, así que cada vuelta gira una celda antes del anillo recorrido la vez anterior. Eso mantiene cada vuelta dentro de la anterior, formando la espiral. El recorrido nunca necesita saber en qué capa está, solo si la siguiente celda está libre.

Python

def spiralOrder(matrix):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]

Esperado

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]