Entrevista técnica de código: Contar el número de islas con DFS iterativo

Problema y cuándo aplica

Dada una cuadrícula m × n que contiene únicamente "1" para tierra y "0" para agua, devuelve el número de islas. Dos celdas de tierra están conectadas solo si comparten un borde horizontal o vertical. Una isla es un conjunto conexo maximal de celdas de tierra.

Las restricciones son 1 <= m, n <= 300. Aun así, la implementación se protege contra un arreglo vacío en lugar de convertir el contrato del llamador en un fallo en tiempo de ejecución. Asume que la cuadrícula se puede modificar. Si el llamador debe conservarla, utiliza en su lugar una matriz visited del mismo tamaño.

Esta es una pregunta general de algoritmos para rondas de programación en ingeniería de software. Evalúa si el candidato puede modelar una matriz como un grafo implícito, recorrer componentes conexas y mantener la implementación consistente con el análisis de complejidad.

Qué evalúa el entrevistador

Una respuesta sólida trata cada celda de tierra como un vértice y cada adyacencia de tierra en cuatro direcciones como una arista. Esto produce la regla clave: cada vez que el escaneo llega a tierra no visitada, ha encontrado una nueva componente conexa. Se cuenta una vez, luego se recorre y se marca toda la isla para que no pueda volver a contarse.

Los detalles de implementación importan. Marca un vecino cuando se agrega a la pila (push), no cuando se extrae (pop); de lo contrario, múltiples celdas adyacentes pueden agregar a la pila la misma celda. El DFS iterativo evita una pila de llamadas profunda del lenguaje cuando la mayor parte de la cuadrícula es una sola isla. Una respuesta precisa también señala que el marcado in-place elimina la matriz visited, mientras que la pila explícita aún puede ocupar O(mn) de espacio en el peor de los casos.

Una respuesta débil simplemente dice “usar DFS” sin definir la conectividad, la mutación de la entrada, un invariante de corrección ni pruebas adversarias.

Preguntas para clarificar primero

¿Las diagonales conectan? Este problema utiliza cuatro direcciones. Si cuentan ocho direcciones, extiende la lista de direcciones y espera que algunas respuestas cambien.
¿Se puede modificar la entrada? En caso afirmativo, convierte las celdas "1" visitadas en "0". De lo contrario, utiliza visited, preservando el límite de tiempo mientras se añade un almacenamiento de O(mn).
¿La cuadrícula es rectangular y no vacía? La descripción garantiza ambas cosas; el código de producción aún puede devolver 0 para una entrada vacía. Un arreglo irregular (jagged array) requeriría límites basados en cada fila.
¿Se trata de un conteo estático único o un conteo después de cada inserción de tierra? DFS o BFS se adaptan a la cuadrícula estática. Las inserciones incrementales favorecen la estructura de conjuntos disjuntos (disjoint set union).
¿Cuáles son los límites de tamaño y de la pila de llamadas? Una cuadrícula de 300×300 compuesta en su totalidad por tierra puede inducir una ruta con 90,000 llamadas recursivas, por lo que esta solución utiliza una pila explícita.

Estructura de respuesta en 30 segundos

“Modelaré las celdas de tierra como vértices en un grafo implícito, con la adyacencia en cuatro direcciones como aristas. Escaneo la cuadrícula fila por fila. Cada 1 restante inicia una componente conexa no procesada, por lo que incremento el conteo de islas y ejecuto un DFS iterativo desde allí. Convierto un vecino de tierra en 0 al hacerle push, lo que previene pushes duplicados. Cada celda se agrega a la pila como máximo una vez, y una pila explícita evita la recursión profunda. La complejidad temporal es O(mn), y la pila es O(mn) en el peor de los casos. Si mutar la entrada está prohibido, almacenaré el mismo estado en una matriz visited.”

Análisis detallado paso a paso

Paso 1: Identificar el trabajo redundante en una búsqueda ingenua

Comenzar una búsqueda nueva desde cada celda de tierra recorrería la misma isla muchas veces. Encontrar vecinos no es el cuello de botella; la pieza faltante es el estado que persiste entre búsquedas y registra que una celda ya pertenece a una componente contada.

Un escaneo completo más marcas permanentes de visita elimina esa repetición. Comienza un recorrido únicamente desde tierra que permanezca sin visitar.

Paso 2: Establecer el invariante de conteo

Cuando el escaneo llega a (r, c), cada DFS anterior ha marcado exactamente una isla completa. Si la celda actual sigue siendo "1", ninguno de esos recorridos la alcanzó, por lo que debe iniciar una nueva isla y el conteo se incrementa en uno.

El DFS sigue únicamente aristas de tierra en cuatro direcciones, por lo que no puede cruzar agua y fusionar islas distintas. También alcanza cada celda de tierra conectada a su inicio, por lo que esta isla no puede provocar otro conteo más adelante. Estos dos hechos demuestran tanto la ausencia de subconteo como la ausencia de doble conteo.

Paso 3: Marcar al momento del push

Supongamos que una celda no marcada toca dos celdas que ya están en la pila. Si el marcado espera hasta el momento del pop, ambos vecinos pueden agregar esa celda a la pila. El resultado a menudo sigue siendo correcto, pero la pila contiene trabajo duplicado y se pierde el argumento estricto de complejidad.

Cambia un vecino descubierto a "0" antes de hacerle push. Cualquier arista posterior lo verá entonces como visitado, garantizando que cada celda de tierra entre a la pila como máximo una vez.

Paso 4: Implementar DFS iterativo

javascript

function numIslands(grid) {
  if (grid.length === 0 || grid[0].length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let islands = 0;

  for (let row = 0; row < rows; row += 1) {
    for (let col = 0; col < cols; col += 1) {
      if (grid[row][col] !== "1") continue;

      islands += 1;
      grid[row][col] = "0";
      const stack = [[row, col]];

      while (stack.length > 0) {
        const [currentRow, currentCol] = stack.pop();

        for (const [rowOffset, colOffset] of directions) {
          const nextRow = currentRow + rowOffset;
          const nextCol = currentCol + colOffset;

          if (
            nextRow >= 0 && nextRow < rows &&
            nextCol >= 0 && nextCol < cols &&
            grid[nextRow][nextCol] === "1"
          ) {
            grid[nextRow][nextCol] = "0";
            stack.push([nextRow, nextCol]);
          }
        }
      }
    }
  }

  return islands;
}

El escaneo inspecciona mn celdas. Cada celda de tierra se agrega a la pila a lo sumo una vez y revisa cuatro vecinos, por lo que el tiempo es O(mn). La pila explícita puede contener O(mn) coordenadas en una cuadrícula completamente de tierra. La función muta su entrada. Copiar la cuadrícula en su lugar también cuesta O(mn) en tiempo y espacio.

Paso 5: Validar límites y casos adversarios

Como mínimo, prueba: un arreglo vacío devuelve 0; una celda de agua devuelve 0; una celda de tierra devuelve 1; todo agua devuelve 0; todo tierra devuelve 1; dos celdas que se tocan solo en diagonal devuelven 2; el ejemplo con tres regiones separadas devuelve 3; y una cuadrícula de 300×300 de solo tierra no desborda la pila de llamadas recursivas.

Prueba también el contrato de mutación. Si otra aserción necesita la cuadrícula original después de la llamada, cópiala primero o usa visited. Esta decisión pertenece al contrato de la interfaz, no como un detalle de implementación oculto.

Paso 6: Comparar alternativas

BFS y DFS iterativo tienen el mismo tiempo y espacio en el peor de los casos aquí. Elige BFS cuando las capas de distancia importen; cualquiera de los dos es apropiado cuando el único objetivo es agotar una componente. El DFS recursivo es más corto solo cuando la entrada es lo suficientemente pequeña o el lenguaje garantiza suficiente profundidad. Disjoint set union es útil cuando la tierra llega incrementalmente y se solicita el conteo después de cada inserción; añade indexación y mantenimiento de conjuntos innecesarios para un solo conteo estático.

Ejemplo de respuesta de alta calidad

“Este problema consiste en contar componentes conexas en un grafo no dirigido implícito. Cada 1 es un vértice, y los vecinos de tierra horizontales o verticales comparten una arista. Escaneo toda la cuadrícula. Si una posición sigue siendo 1, ninguna búsqueda anterior la alcanzó, por lo que he encontrado una nueva isla e incremento el conteo. Luego ejecuto un DFS iterativo y convierto toda esa isla en 0.

Marco los vecinos al hacerles push para que dos celdas adyacentes no puedan agregar a la pila la misma posición. Uso una pila explícita porque una cuadrícula de 300×300 de pura tierra puede producir una ruta recursiva muy profunda. Cada celda se procesa como máximo una vez y comprueba cuatro direcciones, lo que da un tiempo O(mn) y un espacio de pila de O(mn) en el peor de los casos. Esta versión muta la entrada; si la interfaz debe preservarla, moveré las marcas a una matriz booleana visited de tamaño O(mn). Verificaría la no conectividad diagonal, casos de todo agua, todo tierra y límites de entrada vacía.”

Esta respuesta conecta el modelo, el argumento de conteo, el riesgo de implementación, el efecto secundario y la validación sin depender de una etiqueta memorizada.

Errores comunes

Tratar diagonales como conectadas → esto cambia el problema y puede subcontar islas → mantén solo arriba, abajo, izquierda y derecha en la lista de direcciones.
Marcar solo al hacer pop → múltiples vecinos pueden agregar la misma celda a la pila → marca un vecino válido inmediatamente antes de hacer push.
Afirmar que in-place significa espacio O(1) → esto ignora la pila explícita en el peor de los casos → reporta O(mn) de espacio auxiliar en el peor de los casos.
Usar DFS recursivo sin discutir la profundidad → una isla grande puede agotar la pila de llamadas del lenguaje → usa iteración o establece un límite de tamaño seguro.
Mutar los datos del llamador silenciosamente → el código posterior observa una cuadrícula vacía → documenta el efecto secundario o usa visited.
Buscar de nuevo desde cada celda de tierra → se recorre repetidamente la misma componente → comienza solo desde tierra no visitada.
Probar únicamente rectángulos ordinarios → contraejemplos vacíos, de solo agua, solo tierra y diagonales quedan sin probar → cubre casos mínimos, extremos y adversarios.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Qué pasa si no se puede modificar la entrada?

Asigna una matriz booleana m × n y marca una ubicación como visitada al hacerle push. El invariante de conteo y el tiempo O(mn) se mantienen sin cambios; el almacenamiento adicional es explícitamente O(mn). Copiar la entrada tiene el mismo costo asintótico de espacio pero distinta semántica.

Pregunta de seguimiento 2: ¿Qué pasa si las diagonales también conectan?

Expande la lista de direcciones de cuatro a ocho desplazamientos; la estructura del recorrido no cambia. Primero confirma la regla con un caso como [[1, 0], [0, 1]]: la respuesta para cuatro direcciones es 2, mientras que para ocho direcciones es 1.

Pregunta de seguimiento 3: ¿Qué pasa si se agrega tierra celda por celda y se solicita el conteo después de cada una?

Repetir un DFS estático desperdicia trabajo. En su lugar, usa disjoint set union: una nueva celda de tierra inicialmente incrementa el conteo y luego se une con cada vecino de tierra existente. Cada unión exitosa de dos conjuntos diferentes decrementa el conteo. Las inserciones duplicadas deben ignorarse para que no se incrementen dos veces.

Pregunta de seguimiento 4: ¿Qué pasa si el rango de coordenadas es enorme pero la tierra es dispersa?

No asignes la matriz completa. Almacena solo las coordenadas de tierra en un hash set, recorre esas coordenadas y sondea los cuatro vecinos. Con k celdas de tierra, el tiempo esperado es O(k), y el conjunto de visitados más la pila es O(k). Esta conclusión requiere una representación de lista de coordenadas dispersa; no se deriva de una entrada de cuadrícula densa.