Sesión 07: Cracking the Coding Interview (Capítulo 1, Parte 5) — Matrices 2D y Consolidación de Semana 1#

Navegación rápida:

• ← Sesión 06: Strings Avanzados y Compresión
• Sesión 08: Memoria y Selection Sort →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 55-70 minutos.
• Código fuente compilado y probado: practica-rust/dia_07.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

Las matrices bidimensionales representan planos de coordenadas, imágenes y mapas. Comprender su distribución en memoria física es vital para el rendimiento. Consulta el Glosario Maestro.

Matriz Bidimensional y Disposición en Memoria (Row-Major Order)#

• (a) En palabras simples (intuición): Una cuadrícula de ajedrez donde cada casilla tiene fila y columna. En la memoria física de la computadora (que es una sola línea recta de bytes), las cuadrículas se guardan desenrollando una fila completa tras otra.
• (b) Definición técnica paso a paso: Una estructura M × N mapeada a un espacio de direcciones unidimensional. En orden de fila mayoritaria (Row-Major Order, usado por Rust, C y Python):

• (c) Cómo funciona en Rust (memoria y tipos): Un Vec<Vec<T>> es en realidad un vector de punteros en el Stack/Heap hacia vectores dispersos e independientes en el Heap (lo que perjudica la localidad espacial de caché). En sistemas de alto rendimiento se utiliza un vector plano unidimensional continuo Vec<T> de tamaño M × N.
• (d) Error típico de Junior: Recorrer una matriz columna por columna (bucle exterior col, bucle interior row) en un sistema de fila mayoritaria, obligando a la CPU a saltar de línea de caché en cada lectura (cache thrashing).

Transposición de Matriz (Matrix Transpose)#

• (a) En palabras simples (intuición): Doblar la matriz por su diagonal principal (desde la esquina superior izquierda a la inferior derecha), convirtiendo las filas en columnas y las columnas en filas.
• (b) Definición técnica paso a paso: Operación algebraica donde cada elemento en las coordenadas (i, j) se intercambia simétricamente con el elemento en (j, i) para todo j > i.
• (c) Cómo funciona en Rust (memoria y tipos): Se realiza in-place con complejidad temporal O(N²) y cero asignaciones auxiliares (O(1) espacio) iterando sobre el triángulo superior de la matriz.
• (d) Error típico de Junior: Iterar sobre todos los pares (i, j) de $0$ a N, intercambiando dos veces cada celda y regresando la matriz a su estado original idéntico.

Rotación In-Place de 90° en Sentido Horario#

• (a) En palabras simples (intuición): Girar una foto 90 grados a la derecha en la pantalla de tu celular sin guardar una copia duplicada de la imagen en el disco.
• (b) Definición técnica paso a paso: Transformación geométrica que mapea cada coordenada (i, j) a (j, N - 1 - i). Matemáticamente se descompone en dos pasos elementales in-place:

• (c) Cómo funciona en Rust (memoria y tipos): Primero se ejecuta el bucle de transposición in-place y luego se aplica el método nativo de Rust row.reverse() sobre cada fila individual en tiempo lineal.
• (d) Error típico de Junior: Asignar una nueva matriz auxiliar N × N en el Heap, fallando el requerimiento estricto de las entrevistas de operar en O(1) espacio de memoria auxiliar.

Técnica de Banderas en Primera Fila/Columna (In-Place Flagging)#

• (a) En palabras simples (intuición): Para recordar qué habitaciones de un hotel necesitan limpieza sin llevar una libreta extra, pones una pequeña marca en el casillero de la recepción de ese piso.
• (b) Definición técnica paso a paso: Estrategia de ahorro de espacio para problemas de propagación (como Set Matrix Zeroes, LeetCode 73). En lugar de usar conjuntos auxiliares HashSet de filas y columnas (O(M + N) espacio), se reutilizan las celdas de la primera fila y primera columna de la matriz como vectores de estado booleanos.
• (c) Cómo funciona en Rust (memoria y tipos): Se necesitan únicamente dos variables booleanas de 1 byte en el Stack (first_row_has_zero y first_col_has_zero) para salvar el estado de la primera fila y primera columna antes de usarlas como banderas.
• (d) Error típico de Junior: Reemplazar por ceros inmediatamente al encontrar un cero, lo que causa un "efecto dominó" que convierte erróneamente la matriz entera en ceros.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Matemática de la Rotación Matricial: Descomposición Geométrica#

Queremos rotar una matriz cuadrada N × N exactamente 90 grados en sentido horario. Analicemos qué transformación sufren los índices:

• El elemento superior izquierdo (0, 0) debe terminar en el superior derecho (0, N - 1).
• El elemento superior derecho (0, N - 1) debe terminar en el inferior derecho (N - 1, N - 1).
• En general, la celda (i, j) debe terminar en la posición (j, N - 1 - i).

¿Por qué es difícil hacer esto directamente? Porque mover cuatro celdas a la vez en ciclos de 4 requiere una aritmética de capas (rings) compleja y propensa a errores de índice.

Sin embargo, el álgebra lineal nos proporciona una identidad elegante:

1. Transposición:
   (i, j) → (j, i)
2. Reflexión Horizontal (Inversión de cada fila):
   (j, i) → (j, N - 1 - i)

¡La composición de estas dos operaciones básicas produce exactamente la rotación de 90° requerida! Ambas operaciones son extraordinariamente sencillas de escribir, no tienen casos de borde complejos y operan 100% in-place con cero memoria auxiliar.

3. Visualización Paso a Paso y Gráfica de Memoria en Rust#

Flujo de Rotación de Matriz 90° In-Place#

Consulta la arquitectura visual en los diagramas del sistema:

• Gráfico SVG: ![Visualización del Día 07 y Memoria en Rust](../diagrams/sesiones/dia_07.svg)
• Enlace al código fuente Mermaid: Fuente Mermaid

flowchart TD
    M["Matriz Original N x N"] --> TRANS["1. Transponer respecto a diagonal:<br/>swap(matrix[i][j], matrix[j][i]) para j > i"]
    TRANS --> REV["2. Invertir cada fila:<br/>row.reverse()"]
    REV --> RES["Resultado: Matriz rotada 90° en sentido horario in-place O(1) espacio"]

Visualización Cuadro por Cuadro de Memoria: Rotación de Matriz 3 × 3#

Entrada:

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

PASO 1: TRANSPOSICIÓN (Intercambiar matrix[i][j] con matrix[j][i] para j > i)
- Intercambiar (0,1) y (1,0): 2 y 4 se intercambian.
- Intercambiar (0,2) y (2,0): 3 y 7 se intercambian.
- Intercambiar (1,2) y (2,1): 6 y 8 se intercambian.

Matriz transpuesta en memoria:
[ 1,  4,  7 ]
[ 2,  5,  8 ]
[ 3,  6,  9 ]

PASO 2: INVERSIÓN HORIZONTAL DE CADA FILA (row.reverse())
- Fila 0: [ 1, 4, 7 ] -> [ 7, 4, 1 ]
- Fila 1: [ 2, 5, 8 ] -> [ 8, 5, 2 ]
- Fila 2: [ 3, 6, 9 ] -> [ 9, 6, 3 ]

Matriz final rotada 90° en sentido horario:
[ 7,  4,  1 ]
[ 8,  5,  2 ]
[ 9,  6,  3 ]
Cero asignaciones en Heap. Memoria auxiliar: O(1).

4. Implementación Canónica en Rust + Comparativa con Python#

Implementación en Rust (practica-rust/dia_07.rs)#

//! Implementación canónica de algoritmos sobre Matrices 2D en Rust.
//! Compilable y verificable con `rustc --test`.

/// CTCI 1.7 / LeetCode 48: Rota una matriz N x N 90 grados en sentido horario in-place.
pub fn rotate_matrix_in_place(matrix: &mut Vec<Vec<i32>>) {
    let n = matrix.len();
    if n <= 1 {
        return;
    }

    // Paso 1: Transponer respecto a la diagonal principal
    for i in 0..n {
        for j in (i + 1)..n {
            let temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }

    // Paso 2: Invertir horizontalmente cada fila
    for row in matrix.iter_mut() {
        row.reverse();
    }
}

/// CTCI 1.8 / LeetCode 73: Set Matrix Zeroes en O(1) espacio auxiliar con banderas in-place.
pub fn set_matrix_zeroes(matrix: &mut Vec<Vec<i32>>) {
    let rows = matrix.len();
    if rows == 0 {
        return;
    }
    let cols = matrix[0].len();
    if cols == 0 {
        return;
    }

    let mut first_row_has_zero = false;
    let mut first_col_has_zero = false;

    // 1. Verificar si la primera columna tiene ceros originales
    for r in 0..rows {
        if matrix[r][0] == 0 {
            first_col_has_zero = true;
            break;
        }
    }

    // 2. Verificar si la primera fila tiene ceros originales
    for c in 0..cols {
        if matrix[0][c] == 0 {
            first_row_has_zero = true;
            break;
        }
    }

    // 3. Utilizar fila 0 y col 0 como banderas para el subplano interior
    for r in 1..rows {
        for c in 1..cols {
            if matrix[r][c] == 0 {
                matrix[r][0] = 0;
                matrix[0][c] = 0;
            }
        }
    }

    // 4. Anular celdas basadas en las banderas
    for r in 1..rows {
        for c in 1..cols {
            if matrix[r][0] == 0 || matrix[0][c] == 0 {
                matrix[r][c] = 0;
            }
        }
    }

    // 5. Aplicar ceros a la primera columna si correspondía
    if first_col_has_zero {
        for r in 0..rows {
            matrix[r][0] = 0;
        }
    }

    // 6. Aplicar ceros a la primera fila si correspondía
    if first_row_has_zero {
        for c in 0..cols {
            matrix[0][c] = 0;
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_rotate_matrix_in_place() {
        let mut mat = vec![
            vec![1, 2, 3],
            vec![4, 5, 6],
            vec![7, 8, 9],
        ];
        rotate_matrix_in_place(&mut mat);
        let expected = vec![
            vec![7, 4, 1],
            vec![8, 5, 2],
            vec![9, 6, 3],
        ];
        assert_eq!(mat, expected);
    }

    #[test]
    fn test_set_matrix_zeroes() {
        let mut mat = vec![
            vec![1, 1, 1],
            vec![1, 0, 1],
            vec![1, 1, 1],
        ];
        set_matrix_zeroes(&mut mat);
        let expected = vec![
            vec![1, 0, 1],
            vec![0, 0, 0],
            vec![1, 0, 1],
        ];
        assert_eq!(mat, expected);
    }
}

Implementación Canónica en Python (practica/dia_07_matrix_manipulation.py)#

from typing import List

def rotate_matrix_in_place(matrix: List[List[int]]) -> None:
    n = len(matrix)
    # 1. Transponer
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # 2. Invertir cada fila
    for row in matrix:
        row.reverse()

5. Las 3 Trampas Clásicas en Entrevistas#

1. La Cascada Destructiva de Ceros (Zero Matrix): - Si recorres la matriz y cambias inmediatamente la fila y columna a cero, en la siguiente iteración el algoritmo encontrará los ceros que tú mismo acabas de escribir y continuará propagando ceros hasta borrar absolutamente toda la matriz.
2. Intentar Rotar Matrices No Cuadradas In-Place: - Una rotación de 90° de una matriz M × N (donde M ≠ N) da como resultado una matriz N × M. Esto cambia las dimensiones del búfer en memoria y no puede realizarse in-place en un arreglo estático sin memoria auxiliar.
3. El Préstamo Simultáneo de Referencias Mutables en Rust: - En Rust, no puedes escribir swap(&mut matrix[i][j], &mut matrix[j][i]) directamente porque matrix no puede ser prestada como mutable dos veces al mismo tiempo. El código idiomático utiliza una variable temporal let temp = matrix[i][j] o manipulación de slices no solapados con split_at_mut.

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Puente a LeetCode y Práctica de Código#

1. LeetCode 48 — Rotate Image (Medium): - Implementa transposición + inversión horizontal de filas.
2. LeetCode 73 — Set Matrix Zeroes (Medium): - Resuelve en O(1) espacio con marcadores en la fila 0 y columna 0.
3. LeetCode 54 — Spiral Matrix (Medium): - Recorrido con cuatro fronteras móviles (top, bottom, left, right).

Navegación:

• ← Volver a Sesión 06: Strings Avanzados y Compresión
• Avanzar a Sesión 08: Memoria y Selection Sort (Grokking Ch 2) →