Sesión 46: Cracking the Coding Interview (Capítulo 10, Parte 2) — Búsqueda en Matriz 2D, Rank from Stream y Peaks & Valleys#

Navegación rápida:

• ← Sesión 45: CTCI Ch10 — Búsqueda y Ordenamiento: Rotated Array y Búsqueda Binaria Modificada
• Sesión 47: Árboles de Prefijos (Tries): Inserción, Búsqueda y Autocompletado con Comodines →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 65-80 minutos.
• Código fuente compilado y probado: practica-rust/dia_46.rs

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

En esta sesión abordamos la reducción dimensional en matrices bidimensionales ordenadas, el aumento de árboles binarios de búsqueda para flujos continuos y reordenamientos voraces lineales. Consulta el Glosario Maestro y la Guía de Diagramas.

Staircase Matrix Search (Búsqueda en Escalera 2D / CTCI 10.9 & LC 240)#

• (a) En palabras simples (intuición): Imagina un tablero de ajedrez donde los números crecen hacia la derecha y también hacia abajo. Si te paras en el centro, no sabes a dónde moverte porque tanto la derecha como abajo son mayores. Pero si te paras en la esquina superior derecha, ocurre algo mágico: hacia abajo los números crecen, y hacia la izquierda los números decrecen. Tienes una bifurcación perfecta sin ambigüedad: si tu número es menor, te mueves a la izquierda; si es mayor, bajas un piso.
• (b) Definición técnica paso a paso: Algoritmo de eliminación de filas y columnas para matrices de M × N donde cada fila y cada columna están independientemente ordenadas de forma ascendente. Se inicia en (r = 0, c = N - 1):
• Si matrix[r][c] == target: Objetivo hallado.
• Si matrix[r][c] > target: Como todos los elementos bajo la columna c son aún mayores, toda la columna c queda descartada ⟹ c = c - 1.
• Si matrix[r][c] < target: Como todos los elementos a la izquierda en la fila r son aún menores, toda la fila r queda descartada ⟹ r = r + 1.
• Complejidad: A lo sumo M + N pasos ⟹ O(M + N) tiempo y O(1) espacio.
• (c) Cómo funciona en Rust (memoria y tipos): La coordenada de columna debe manejarse con cuidado para no subdesbordar usize (usando isize o validando c > 0).
• (d) Error típico de Junior: Intentar arrancar en la esquina superior izquierda (0, 0); en (0, 0) tanto moverte a la derecha como abajo incrementa el valor, impidiendo tomar una decisión unívoca.

Flattened 2D Binary Search (Matriz Aplanada / LeetCode 74)#

• (a) En palabras simples (intuición): Imagina que tomas las páginas de un libro ordenado y las pegas una tras otra en una sola tira larguísima. Aunque en la pantalla se vea como una cuadrícula con filas y columnas, matemáticamente es una sola línea recta de números estrictamente crecientes. Puedes aplicar búsqueda binaria estándar como si fuera un arreglo unidimensional.
• (b) Definición técnica paso a paso: Mapeo biyectivo entre un índice 1D k ∈ [0, M · N - 1] y las coordenadas 2D (r, c) de una matriz de tamaño M × N:

Permite ejecutar búsqueda binaria clásica en O(log(M · N)) tiempo y O(1) espacio auxiliar.

• (c) Cómo funciona en Rust (memoria y tipos): Se calcula mid = left + (right - left) / 2, y luego r = mid / cols, c = mid % cols.
• (d) Error típico de Junior: Confundir LeetCode 74 (donde el primer elemento de la fila i+1 es estrictamente mayor que el último de la fila i) con LeetCode 240 (donde las filas solo están ordenadas internamente y no existe continuidad entre renglones).

Augmented Binary Search Tree (BST Aumentado para Rank from Stream / CTCI 10.10)#

• (a) En palabras simples (intuición): Imagina un árbol genealógico donde cada persona lleva una libreta que anota cuántos descendientes tiene a su mano izquierda. Cuando entra un estudiante nuevo a una fila continua de notas escolares y preguntas: "¿cuántos estudiantes sacaron una nota menor o igual que yo?", la persona en la cima del árbol puede responderte casi al instante sumando las libretas sin tener que contar a todos los alumnos uno por uno.
• (b) Definición técnica paso a paso: Estructura de datos en árbol binario de búsqueda donde cada nodo almacena un campo adicional:

• Inserción de x: Si x ≤ node.val, se incrementa node.left_size += 1 y se desciende por la izquierda; si x > node.val, se desciende por la derecha sin modificar left_size.
• Consulta de Rango (get_rank(x)):
• Si x == node.val ⟹ retorna node.left_size.
• Si x < node.val ⟹ retorna node.left.get_rank(x).
• Si x > node.val ⟹ retorna node.left_size + 1 + node.right.get_rank(x).
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa mediante punteros inteligentes en el Heap con Option<Box<RankNode>>.
• (d) Error típico de Junior: Mantener un vector ordenado e insertar con insert() en cada número nuevo, lo que causa desplazamientos masivos en memoria de costo O(N) por inserción.

Peaks and Valleys (Secuencia Alternante Voraz / CTCI 10.11)#

• (a) En palabras simples (intuición): Tienes personas formadas en fila y quieres que queden en una silueta de serrucho o cordillera: una persona alta, una baja, una alta, una baja (A ≤ B ≥ C ≤ D ≥ E). En lugar de ordenar a todos de menor a mayor y luego cambiarlos de lugar, caminas de dos en dos pasos y te aseguras de que la persona del centro sea más alta que sus dos vecinos de los lados mediante un simple intercambio local.
• (b) Definición técnica paso a paso: Algoritmo voraz (greedy) in-place que transforma un arreglo en tiempo lineal O(N) y espacio O(1) sin ordenar previamente. Se itera únicamente sobre los índices impares i = 1, 3, 5, …:
• Se identifica el índice del valor máximo del trío {A[i-1], A[i], A[i+1]}.
• Si el máximo no es A[i], se intercambia A[i] con dicho máximo.
• Como A[i] recibe el valor mayor local, la relación con el valle anterior A[i-1] jamás puede ser violada.
• (c) Cómo funciona en Rust (memoria y tipos): Se ejecuta sobre un slice mutable nums: &mut [i32] usando nums.swap(i, max_idx).
• (d) Error típico de Junior: Iterar por todos los índices contiguos (i = 0, 1, 2, 3…); al corregir la posición i+1 se puede romper la relación ya establecida en i-1.

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

La Geometría de Staircase Matrix Search (O(M + N))#

Consideremos una matriz ordenada por filas y columnas:

Matriz:
[  1,   4,   7,  11,  15 ]
[  2,   5,   8,  12,  19 ]
[  3,   6,   9,  16,  22 ]
[ 10,  13,  14,  17,  24 ]
[ 18,  21,  23,  26,  30 ]

Queremos buscar el número 5.

1. Punto de inicio: Esquina superior derecha: fila $0$, columna $4$. Valor actual: 15. - ¿15 == 5? No. - ¿15 > 5? Sí. Como la matriz está ordenada hacia abajo en cada columna, todos los elementos de la columna 4 son ≥ 15. Por tanto, el número $5$ no puede residir en ninguna celda de la columna 4. - Eliminamos la columna 4: c = c - 1 = 3.
2. Posición: (0, 3). Valor: 11. - 11 > 5 ⟹ Eliminamos la columna 3: c = 2.
3. Posición: (0, 2). Valor: 7. - 7 > 5 ⟹ Eliminamos la columna 2: c = 1.
4. Posición: (0, 1). Valor: 4. - ¿4 > 5? No, 4 < 5. - Como la fila 0 está ordenada hacia la izquierda de menor a mayor, todos los elementos a la izquierda de 4 son ≤ 4. Por tanto, el número $5$ no puede estar en la fila 0. - Eliminamos la fila 0: r = r + 1 = 1.
5. Posición: (1, 1). Valor: 5. - ¿5 == 5? ¡Sí! Retornamos coordenadas (1, 1).

Demostración de Cota Temporal: En cada iteración descartamos exactamente una fila entera (r se incrementa) o una columna entera (c se decrementa). Como solo hay M filas y N columnas, el bucle ejecuta como máximo M + N pasos. Tiempo total: O(M + N).

Demostración Matemática: Invariante Voraz de Peaks and Valleys#

¿Por qué intercambiar A[i] con el máximo del trío {A[i-1], A[i], A[i+1]} jamás destruye la condición de pico/valle previamente establecida en i - 2?

Supongamos que hasta el índice i - 1 la condición ya se cumplía:

Es decir, A[i-1] ya era un valle legal respecto al pico anterior A[i-2].

Ahora evaluamos el pico en la posición impar i. Sea M = max(A[i-1], A[i], A[i+1]).

• Si M = A[i], no hay intercambio y A[i] ≥ A[i-1]. La propiedad se mantiene.
• Si M = A[i-1], intercambiamos A[i] con A[i-1]. El nuevo valor en la posición i-1 es el valor que antes estaba en i. Como A[i] ≤ M, el nuevo valor en i-1 es menor o igual al valor original de A[i-1].

En consecuencia:

¡El valle anterior se vuelve aún más profundo o se mantiene idéntico! Jamás superará al pico A[i-2].

Esta prueba inductiva formal garantiza que una sola pasada hacia adelante sin backtracking (O(N)) resuelve el problema óptimamente.

3. Visualización de Arquitectura y Memoria en Rust#

Diagrama de Eliminación en Escalera#

Consulta el diagrama vectorial:

flowchart TD
    START["Posición inicial: r = 0, c = cols - 1"] --> CHECK{"¿matrix[r][c] == target?"}
    CHECK -->|Sí| FOUND["Retornar Some((r, c))"]
    CHECK -->|No| CMP{"¿matrix[r][c] > target?"}
    CMP -->|Sí: Columna descartada| COL["c = c - 1<br/>(Avanza a la izquierda)"]
    CMP -->|No: Fila descartada| ROW["r = r + 1<br/>(Avanza hacia abajo)"]
    COL --> BOUNDS{"¿r < rows && c >= 0?"}
    ROW --> BOUNDS
    BOUNDS -->|Sí| CHECK
    BOUNDS -->|No: Fuera de matriz| NOT_FOUND["Retornar None"]

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Estructura de memoria de un RankTracker tras insertar stream = [5, 1, 9]:

STACK:
[ tracker: RankTracker { root: Some(0x7fff_node_5) } ]

HEAP:
Dirección: 0x7fff_node_5
┌────────────────────────────────────────────────────────┐
│ RankNode { val: 5, left_size: 1 }                      │
│ left:  Some(Box -> 0x7fff_node_1)                      │
│ right: Some(Box -> 0x7fff_node_9)                      │
└────────────────────────────────────────────────────────┘
            │                                   │
            ▼                                   ▼
Dirección: 0x7fff_node_1            Dirección: 0x7fff_node_9
┌──────────────────────────────┐    ┌──────────────────────────────┐
│ RankNode { val: 1,           │    │ RankNode { val: 9,           │
│            left_size: 0 }    │    │            left_size: 0 }    │
│ left: None, right: None      │    │ left: None, right: None      │
└──────────────────────────────┘    └──────────────────────────────┘

EJECUCIÓN DE tracker.get_rank_of_number(9):
1. Compara 9 con root (5): 9 > 5.
2. Desciende a la derecha: root.left_size (1) + 1 + right.get_rank(9).
3. En node_9: 9 == 9 -> retorna node_9.left_size = 0.
4. Total acumulado: 1 + 1 + 0 = 2.
Resultado: exactamente 2 elementos (1 y 5) son menores que 9.

4. Las 3 Trampas Clásicas en Entrevistas y Cómo Evitarlas#

Trampa 1: Confundir las Condiciones de LeetCode 74 y LeetCode 240#

• El error: Aplicar la búsqueda binaria aplanada O(log(M · N)) a una matriz de LeetCode 240.
• Por qué falla: En LeetCode 240, el último elemento de la fila 0 puede ser 15, mientras que el primer elemento de la fila 1 puede ser 2. La matriz no es monótona de forma global si se desenrolla en 1D; solo lo es dentro de cada fila y columna por separado.
• La solución: Usar la búsqueda en escalera O(M + N) para LeetCode 240 y reservar el aplanamiento O(log(M · N)) exclusivamente para matrices con orden global contiguo (LeetCode 74).

Trampa 2: Olvidar el + 1 al Descender a la Rama Derecha en RankNode#

• El error: Escribir self.left_size + right.get_rank(x) sin sumar 1.
• Por qué falla: Si x es mayor que el valor del nodo actual, x no solo es mayor que todos los elementos del subárbol izquierdo (left_size), sino que también es mayor que el propio nodo actual.
• La solución: Sumar obligatoriamente self.left_size + 1 + right_rank:

  Some(self.left_size + 1 + right_rank)

Trampa 3: Sobrescribir Índices Fuera de Límite en Peaks and Valleys#

• El error: Evaluar nums[i + 1] en la última posición impar sin comprobar si i + 1 < n.
• Por qué falla: Si el arreglo tiene una cantidad par de elementos (por ejemplo, longitud 4, índices 0, 1, 2, 3), cuando i = 3, i + 1 = 4, lo que causa un pánico de acceso fuera de límites en Rust.
• La solución: Proteger siempre el vecino derecho con if i + 1 < n:

  if i + 1 < n && nums[i + 1] > nums[max_idx] {
      max_idx = i + 1;
  }

5. Implementación Canónica en Rust y Comparativa con Python#

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

/// CTCI 10.9 / LeetCode 240: Staircase Matrix Search O(M + N).
pub fn matrix_search_2d_coords(matrix: &[Vec<i32>], target: i32) -> Option<(usize, usize)> {
    if matrix.is_empty() || matrix[0].is_empty() {
        return None;
    }

    let rows = matrix.len();
    let cols = matrix[0].len();
    let mut r = 0usize;
    let mut c = cols as isize - 1;

    while r < rows && c >= 0 {
        let val = matrix[r][c as usize];
        if val == target {
            return Some((r, c as usize));
        } else if val > target {
            c -= 1;
        } else {
            r += 1;
        }
    }

    None
}

/// CTCI 10.10: BST Aumentado para Rank from Stream.
#[derive(Debug)]
struct RankNode {
    val: i32,
    left_size: usize,
    left: Option<Box<RankNode>>,
    right: Option<Box<RankNode>>,
}

impl RankNode {
    fn new(val: i32) -> Self {
        Self {
            val,
            left_size: 0,
            left: None,
            right: None,
        }
    }

    fn insert(&mut self, x: i32) {
        if x <= self.val {
            self.left_size += 1;
            match self.left.as_mut() {
                Some(left_child) => left_child.insert(x),
                None => self.left = Some(Box::new(RankNode::new(x))),
            }
        } else {
            match self.right.as_mut() {
                Some(right_child) => right_child.insert(x),
                None => self.right = Some(Box::new(RankNode::new(x))),
            }
        }
    }

    fn get_rank(&self, x: i32) -> Option<usize> {
        if x == self.val {
            Some(self.left_size)
        } else if x < self.val {
            self.left.as_ref().and_then(|child| child.get_rank(x))
        } else {
            self.right
                .as_ref()
                .and_then(|child| child.get_rank(x))
                .map(|r_rank| self.left_size + 1 + r_rank)
        }
    }
}

/// CTCI 10.11: Peaks and Valleys en O(N) Voraz.
pub fn peaks_and_valleys(nums: &mut [i32]) {
    let n = nums.len();
    if n <= 1 {
        return;
    }

    let mut i = 1;
    while i < n {
        let mut max_idx = i;
        if nums[i - 1] > nums[max_idx] {
            max_idx = i - 1;
        }
        if i + 1 < n && nums[i + 1] > nums[max_idx] {
            max_idx = i + 1;
        }
        if max_idx != i {
            nums.swap(i, max_idx);
        }
        i += 2;
    }
}

Implementación de Referencia en Python (practica/dia_46_matrix_search_rank_stream.py)#

from typing import List, Optional, Tuple


def matrix_search_2d(matrix: List[List[int]], target: int) -> bool:
    """CTCI 10.9 / LC 240: Búsqueda en escalera desde esquina superior derecha."""
    if not matrix or not matrix[0]:
        return False

    rows, cols = len(matrix), len(matrix[0])
    r, c = 0, cols - 1

    while r < rows and c >= 0:
        val = matrix[r][c]
        if val == target:
            return True
        elif val > target:
            c -= 1
        else:
            r += 1

    return False


class RankNode:
    """CTCI 10.10: BST Aumentado con left_size."""

    def __init__(self, val: int) -> None:
        self.val = val
        self.left: Optional["RankNode"] = None
        self.right: Optional["RankNode"] = None
        self.left_size: int = 0

    def insert(self, x: int) -> None:
        if x <= self.val:
            self.left_size += 1
            if self.left:
                self.left.insert(x)
            else:
                self.left = RankNode(x)
        else:
            if self.right:
                self.right.insert(x)
            else:
                self.right = RankNode(x)

    def get_rank(self, x: int) -> int:
        if x == self.val:
            return self.left_size
        elif x < self.val:
            return self.left.get_rank(x) if self.left else -1
        else:
            right_rank = self.right.get_rank(x) if self.right else -1
            return -1 if right_rank == -1 else self.left_size + 1 + right_rank

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

7. Ejercicios de Práctica Independiente y Casos Límite#

1. Paso Límite 1: Matriz de 1x1 y Elemento Inexistente: - Prueba matrix_search_2d(&[vec![5]], 5) y matrix_search_2d(&[vec![5]], 3). Verifica que responde true y false respectivamente sin desbordar índices.
2. Paso Límite 2: Flujo con Elementos Duplicados en RankTracker: - Inserta [5, 5, 5, 5]. Verifica que la consulta de tracker.get_rank_of_number(5) responda correctamente 3 (la cantidad de 5s insertados previamente a la izquierda).
3. Paso Límite 3: Peaks and Valleys con Elementos Todos Iguales: - Prueba peaks_and_valleys(&mut [2, 2, 2, 2, 2]). Verifica que el arreglo conserve su validez formal ya que 2 ≤ 2 ≥ 2 ≤ 2 ≥ 2.

Navegación final:

• ← Sesión 45: CTCI Ch10 — Búsqueda y Ordenamiento: Rotated Array y Búsqueda Binaria Modificada
• Sesión 47: Árboles de Prefijos (Tries): Inserción, Búsqueda y Autocompletado con Comodines →
• Glosario Maestro
• Guía de Diagramas de Arquitectura