Thread by @charliesbot

Hora de un ⚡️#thread! Vamos a trabajar un poco más los ejercicios que preguntan en la entrevista enfocada a algoritmos en que preguntan en #FAANG

Este es mi favorito -> Number of islands.

Es un ejercicio de nivel medio.

leetcode.com/problems/numbe…

En este ejercicio vamos a ver un algoritmos llamado DFS. Voy a tratar de explicarlo lo más sencillo posible. Pero lee este thread tantas veces lo necesites, y pregúntame las dudas que tengas.

Lo importante es que DFS te haga click 🧑🏽‍💻

El ejercicio Number of Islands dice:
Tenemos un array de m * n, lleno de valores “1” y “0”.

1 representa tierra, y 0 el mar.

Una isla esta representada por varios 1 contiguos.

Cuántas islas hay en los arrays que nos den?

Pongámosle un poco de color a lo que estamos buscando.

En el ejemplo, están iluminados los grupos de 1s contiguos que representan islas.

En este caso, tenemos 3 islas!

Antes de continuar: cómo se te ocurre hacerlo?

Recuerda que hay mil formas de resolver este tipo de ejercicios.

Lo que estamos haciendo con estos threads es tener más herramientas a la mano y poder elegir la que nos haga el trabajo más fácil!

Como este es mi ejercicio favorito, ya tengo en mente la solución que usaría!

Y para poder resolverlo, tenemos que sacar de la caja de herramientas el algoritmo DFS.

DFS es un algoritmo para recorrer grafos.

DFS, o Depth First Search, es un algoritmo que recorre los paths de un grafo a profundidad.

Qué significa esto? Que conforme avanzamos en el grafo, vamos a visitar los nodos de alrededor. Y así hasta que no haya más nodos en ese camino.

Pero bueno! Lo mejor es que lo expliquemos paso a paso!

Aquí tenemos un grafo, muchos nodos y muchas flechas que nos indican la dirección.

2 reglas de DFS

- No importa en que nodo comiences. En los grafos, a diferencia de los árboles, no hay un solo padre!
- Un nodo no se puede visitar dos veces. Super importante 🚨

DFS usa un stack para saber el camino que estamos creando al visitar los nodos.

En esta ocasión, elegiré “a” para empezar. Y lo pondré en el stack para saber el camino que estoy creando.

a tiene que nodos vecinos: b,c y g. Podemos elegir cualquiera para avanzar.

Elijo “c” y lo pongo en el stack.

c solo tiene un vecino -> d. Ponemos d en el stack y avanzamos

d tiene dos vecinos: e y f. En esta ocasión elijo a e, lo ponemos en el stack y avanzamos.

Y ahora vemos porque DFS es acerca de búsqueda en profundidad: agarramos un solo camino, y paramos hasta llegar al final.

e es el final de este camino.

Lo sacamos del stack, y ahora ese stack nos dice que el paso previo era d!

El vecino de d que queda por visitar es f.

De f nos vamos a g! Y guardamos g en el stack.

Antes de seguir, cual crees que sea el siguiente paso? Visitar c?

Nope! Recuerda: solo podemos visitar cada nodo una sola vez. Y ya visitamos a c antes.

Por lo tanto, este camino esta completo.

Retrocedemos todos los pasos que tenemos en el stack, y nos damos cuenta que solo queda un vecino de a por checar: a -> b

Y de nuevo, b tiene dos vecinos, d y e.

Pero estos ya fueron visitados antes, por lo que hemos recorrido todo el grafo!

Este es el poder de DFS.

Pero, cómo vamos a aplicar DFS en el ejercicio de Number of Islands?

🌟 Bueno, lo que decía el ejercicio number of islands es que nos iban a dar data en forma de un array m * n.

O sea, un array m* n es una matriz.

Y las matrices son grafos!

🧑🏽‍💻 Aún no hemos codeado porque necesitamos definir nuestra estrategia.

Ya sabemos que un DFS nos va a ayudar.

Ahora tracemos el algoritmo antes de codear.

Para hacer más visual el ejemplo, a cada elemento le asigné una letra. Cada elemento es un índice de la matriz, que realmente se podría acceder de la forma array[i][j]

Pero para cuestiones prácticas, las letras serán lo mismo.

Empezamos con 0 islas.

Comenzamos a recorrer la lista. Si empezamos desde array[0][0], significa que nuestro primer paso es desde A.

A tiene un valor de 1. Descubrimos un pedazo de una isla! Pero no sabemos aún de que tamaño es la isla.

Hora del DFS!

Primero incrementamos el contador de islas a 1.

Mmmm, necesitamos registrar de alguna forma que este nodo fue visitado.

Qué tal si cambiamos los 1s que encontramos a 0s? Si es un 0, ya sabemos que no tenemos que tomar acciones extras!

Cambiar los 1s a 0s nos ayudará a simplificar nuestro algoritmos.

Nuestra condición será:

- Si el nodo es 1, sigue avanzando.
- Si es 0, encontramos el final de un camino. Hora de parar.

Los vecinos de A son B y F.

Vamos a recorrer a los vecinos con algún patrón.

Yo elegiré arriba, derecha, abajo, izquierda. Si el vecino se sale del array, será undefined.

En esta ocasión, arriba es undefined, derecha es B, abajo es F e izquierda es undefined.

Dado que no hay valor hacia arriba, nos vamos al vecino de la derecha, que es B.

Nuestra meta cuando estamos buscando vecinos es ver que tan grande es la isla!

Y luego volvemos a hacer lo mismo: cambiamos el valor de 1 a 0, y buscamos nuevos vecinos.

Hora de moverse a C!

Y de nuevo! Cambiamos C de 1 a 0.

Este va a ser el patrón del algoritmo!

Checamos vecinos: D y H. Pero ambos son 0, por lo que llegamos al final de este camino.

A movernos unos pasos atrás.

Volvemos a B! Y en esta ocasión, nos movemos a G.
Transformamos G de 1 a 0, y proseguimos a F.
Ya casi terminamos este camino!

Y de nuevo! Estando en F, lo cambiamos de 1 a 0.

Los vecinos de F son 0, por lo que hemos llegado de nuevo a otro final!

Recorremos todos los pasos hacia atrás que teníamos guardados en el stack, y volvemos a A.

Esto significa que transformamos toda la isla de 1 a 0. Y esto nos va a ayudar en el futuro a no confundirnos conforme buscamos más islas.

Este DFS se acabó.

Seguimos recorriendo nuestra matriz. Nos habíamos quedado en A.

Vamos a seguir moviéndonos hasta encontrar otros 1.

Y esta ocasión, ese 1 está en E.

Recuerda! Cuando encontramos un 1 desde nuestro recorrido en la matriz, significa que encontramos una isla, y por ende, nuestro contador de islas incrementa.

Ahora tenemos 2 islas!

Transformamos E en 0, y comenzamos un nuevo DFS!

Ah! Pero este DFS estuvo cortísimo! 😅 Los vecinos de E ya son 0.

No hay nada más que transformar!

DFS termina, y seguimos recorriendo este grafo.

Aquí ya podemos ver las ventajas de haber transformado los 0s en 1s. Conforme seguimos recorriendo, no tenemos que hacer cosas complicadas para saber si algo era una isla antes o no.

Nuestro algoritmo solo es: si encuentras un 1, es el principio de una isla.

Cambiamos I de 1 a 0, e incrementamos el contador de islas a 3.

Y volvemos a elegir como vamos a visitar a los vecinos
- Arriba D -> es 0, lo saltamos
- Derecha J -> es 0, lo saltamos
- Abajo H -> es 1, a visitar!

Cambiamos H a 0, y de nuevo, a visitar vecinos.

En esta ocasión solo nos queda O. Cambiamos O por un 0, y…

Hemos acabado el DFS del nodo I!

Seguimos recorriendo el resto de la matriz, y ahora si, ya no encontramos más 1s.

Significa que el resultado final fueron 3 islas!

💡Ahora si, ya tenemos una buena estrategia. Conocemos los patrones que se repiten y el algoritmo que vamos a usar.

Hora de codear!

Empecemos con lo básico

Lo que tenemos que hacer sin duda alguna es recorrer el grafo.

El grafo se representa como un array de arrays, donde el primer array son las filas y el otro array las columnas.

Por ello necesitamos dos for -> #javascript

Ahora, recuerdas que todo empezaba cuando encontramos un “1” ?

Necesitamos una condición. Cuando encontremos “1”, incrementamos el contador de islas, e invocamos nuestro DFS.

Vamos a necesitar pasarle el grafo y los indices de donde vamos a comenzar.

🌟 Para el DFS necesitábamos 1 stack para saber el camino que estábamos recorriendo.

Pero… no necesitamos explícitamente esa estructura.

Normalmente, los DFS se estructuran usando *recursión*

La recursión es un stack de llamadas!

El primer paso del dfs es transformar el nodo en un 0!

Ahora nos falta decirle que tiene que moverse entre los vecinos.

Hora de la recursión.

Dentro de dfs, volvemos a llamar a dfs!

Para movernos, solo tenemos que enviar los indices que ya teníamos, pero con incrementos o decrementos, para movernos arriba, derecha, izquierda, abajo.

Pero, esta recursión nunca va a parar! Nos falta decirle cuando detenerse.

Una condición más será suficiente.

Nuestra recursión debe parar si:
- El valor del nodo es 0
- No hay más filas a donde moverse
- No hay más columnas a donde moverse

🌟 Y listo! DFS nos ayudó a simplificar nuestro problema.

El hecho de saber que existe DFS nos ayuda a aplicar algoritmos comunes a cualquier tipo de problemas, y poder tener una base sólida sobre la cual resolver problemas más complejos.

⚡️ Lo que se busca en las entrevistas no es dejar un ejercicio difícil, o platicar de temas que no se tocan en el día a día.

Es descubrir como pensamos y juntamos muchos elementos pequeños para crear soluciones sólidas.

Y esto es todo! Este ⚡️#thread estuvo largo, pero DFS es de mis algoritmos favoritos.

No es fácil de entender a la primera, así que siéntete con la confianza de preguntarme las dudas que tengas.

Nos vemos pronto en otro ⚡️#thread de “Ejercicios de la entrevista enfocada a algoritmos en FAANG!” #javascript