Aprenda Valid Parentheses, Reverse Linked List e Tree Max Depth com visualização passo a passo no DSA View View 👀👀

Oi oi!

Eu sou @nyaomaru, engenheiro frontend que está sofrendo para criar efeitos sonoros para jogos. 😿

Você já usou o DSA View View? 👀👀

https://dev.to/nyaomaru/i-built-a-tool-to-visualize-dsa-lets-learn-together-dsa-view-view--djo

O DSA View View permite entender DSA visualizando como sua implementação realmente roda.

No artigo anterior, vimos três problemas:

Two Sum
Binary Search
Bubble Sort

https://dev.to/nyaomaru/is-learning-dsa-boring-lets-use-dsa-view-view-two-sum-binary-search-and-bubble-sort-374o

Desta vez, vamos tentar mais três problemas clássicos:

Valid Parentheses
Reverse Linked List
Maximum Depth of Binary Tree

Cada um deles apresenta uma forma de pensar completamente diferente:

Stack
Pointer manipulation
Recursion

E os três podem ficar confusos quando olhamos apenas para o code final.

Então vamos ver o que realmente acontece durante a execução. 👀

Eu também ainda estou aprendendo DSA, então vamos aprender juntos! 😸

🥞 Valid Parentheses

Vamos começar com Valid Parentheses.

Imagine esta string:

()[]{}

Cada opening bracket possui um closing bracket correspondente.

Então ela é valid. ✅

Mas esta aqui:

([)]

é invalid. ❌

Por quê?

Porque os brackets são fechados na ordem errada.

(
  [
)
  ]

O [ precisa ser fechado antes do (.

Então como podemos guardar essa ordem? 🤔

Vamos usar uma Stack

Uma stack segue uma regra bem simples:

A última coisa que colocamos é a primeira que retiramos.

Isso é chamado de LIFO — Last In / First Out.

Imagine uma pilha de pratos.

    🍽️  ← retirar primeiro
    🍽️
    🍽️

O último prato colocado no topo é o primeiro que podemos retirar.

Com parentheses acontece a mesma coisa.

Se vemos:

(
[
{

os brackets precisam ser fechados na ordem inversa:

}
]
)

Por isso, uma stack combina muito bem com esse problema.

A implementação fica assim:

function isValid(s: string): boolean {
  const stack: string[] = [];

  const pairs: Record<string, string> = {
    ")": "(",
    "]": "[",
    "}": "{",
  };

  for (const char of s) {
    if (char === "(" || char === "[" || char === "{") {
      stack.push(char);
      continue;
    }

    if (stack.length === 0) return false;

    const target = stack.pop();

    if (target !== pairs[char]) {
      return false;
    }
  }

  return stack.length === 0;
}

A parte importante é observar como o conteúdo de stack muda.

Vamos usar:

([])

No começo:

stack = []

Primeiro aparece:

É um opening bracket.

Então fazemos push.

stack = ["("]

Depois aparece:

Push novamente.

stack = ["(", "["]

Agora aparece:

É um closing bracket.

O que ele precisa fechar?

E o que está no topo da stack?

Perfect! ✅

Então removemos esse item.

stack = ["("]

Por fim aparece:

Ele precisa fechar:

E o topo da stack também é:

Pop!

stack = []

Chegamos ao final com a stack vazia.

Valid! 🎉

E quando é Invalid?

Agora vamos usar:

([)]

O começo é igual.

(
↓
stack = ["("]

[
↓
stack = ["(", "["]

Então aparece:

O ) precisa encontrar:

Mas o topo da stack é:

Eles não correspondem.

expected: (
actual:   [

Então já sabemos imediatamente que a string é invalid.

Complexity

Percorremos a string apenas uma vez.

Time:  O(n)
Space: O(n)

No pior caso, todos os caracteres podem ser opening brackets e acabar dentro da stack.

👀 Vamos visualizar

É aqui que a stack fica muito mais fácil de entender.

Quando vemos apenas:

stack.push(char);

stack.pop();

é fácil perder de vista o que realmente existe dentro da stack naquele momento.

Especialmente com algo como:

({[]})

Qual bracket está no topo agora?

Qual opening bracket estamos tentando fechar?

Em vez de guardar tudo na cabeça, podemos acompanhar a stack mudando step-by-step.

https://dsa-view-view.vercel.app/#s=j.eyJlIjoidmFsaWQtcGFyZW50aGVzZXMiLCJsIjoidHlwZXNjcmlwdCIsIm0iOiJ2ZXJpZmljYXRpb24iLCJ2IjoxfQ

Conceitualmente, vemos algo assim:

(
↓
[(]

{
↓
[(, {]

[
↓
[(, {, []

]
↓
[(, {]

}
↓
[(]

)
↓
[]

É isso.

Guarde os opening brackets e sempre tente combinar primeiro o item mais recente.

Quando vemos dessa forma, stack deixa de parecer algo tão misterioso. 🥞😸

🔗 Reverse Linked List

Agora vamos inverter uma linked list.

Imagine:

1 → 2 → 3 → 4 → 5

Queremos chegar a:

5 → 4 → 3 → 2 → 1

À primeira vista parece simples.

É só inverter!

Mas linked lists são um pouco diferentes de arrays.

Em um array, os values ficam em positions como estas:

0  1  2  3  4
↓  ↓  ↓  ↓  ↓
1  2  3  4  5

Já uma linked list é formada por nodes que apontam para o próximo node.

1 → 2 → 3 → 4 → 5 → null

Cada seta importa.

Para inverter a list, precisamos inverter essas setas.

1 ← 2 ← 3 ← 4 ← 5

E é aqui que começa a ficar confuso.

Porque, se mudarmos uma seta cedo demais...

podemos perder o resto da list. 😿

Três Variables Importantes

Uma solução iterativa comum usa três variables:

prev
current
next

A implementação é esta:

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let current = head;

  while (current !== null) {
    const next = current.next;

    current.next = prev;

    prev = current;
    current = next;
  }

  return prev;
}

É curta.

Mas muita coisa acontece nessas poucas linhas.

Vamos acompanhar com calma.

Começamos com:

1 → 2 → 3 → null

prev = null
current = 1

Step 1: Salvar o próximo Node

Primeiro:

const next = current.next;

Então:

next = 2

Por que precisamos disso?

Porque daqui a pouco vamos mudar:

1 → 2

Se mudarmos essa seta sem lembrar do 2, perdemos o acesso ao restante da list.

Então, primeiro:

Salve para onde precisamos ir depois.

Step 2: Inverter a Seta

Agora:

current.next = prev;

Originalmente:

1 → 2

Mas prev é:

null

Então agora temos:

1 → null

A primeira seta foi invertida.

Step 3: Mover `prev`

Depois:

prev = current;

Então:

prev = 1

Step 4: Mover `current`

Por fim:

current = next;

Nós salvamos 2 antes.

Então agora:

current = 2

Nosso state fica assim:

null ← 1    2 → 3 → null
       ↑    ↑
      prev current

Depois fazemos exatamente a mesma coisa de novo.

Salvar:

next = 3

Inverter:

2 → 1

Mover:

prev = 2
current = 3

Agora:

null ← 1 ← 2    3 → null
            ↑    ↑
           prev current

Mais uma vez.

next = null

Inverter:

3 → 2

Mover:

prev = 3
current = null

Agora:

null ← 1 ← 2 ← 3
               ↑
              prev

O loop termina porque:

current === null

E prev é o novo head.

Então:

return prev;

Done! 🎉

Complexity

Visitamos cada node uma vez.

Time:  O(n)
Space: O(1)

Não criamos outra linked list.

Só movemos alguns pointers.

👀 Vamos visualizar

Esse é exatamente o tipo de code que eu acho difícil de entender apenas lendo.

Estas quatro linhas:

const next = current.next;
current.next = prev;
prev = current;
current = next;

parecem simples.

Mas, quando vejo um code assim pela primeira vez, meu cérebro começa:

Espera.

- Onde current está agora?
- A gente perdeu next?
- Qual seta mudou?
- Para onde prev está apontando?

😿

https://dsa-view-view.vercel.app/#s=j.eyJlIjoicmV2ZXJzZS1saXN0IiwibCI6InR5cGVzY3JpcHQiLCJtIjoidmVyaWZpY2F0aW9uIiwidiI6MX0

Quando visualizamos cada step, conseguimos realmente acompanhar os pointers se movendo.

prev      current
 ↓           ↓
null         1 → 2 → 3

      ↓↓↓

null ← 1     2 → 3
       ↑     ↑
      prev current

      ↓↓↓

null ← 1 ← 2     3
            ↑     ↑
           prev current

      ↓↓↓

null ← 1 ← 2 ← 3
               ↑
              prev

O algoritmo fica muito mais simples quando paramos de pensar nele como quatro assignments misteriosos.

Na prática é só:

Salvar next
  ↓
Inverter a seta
  ↓
Mover prev
  ↓
Mover current
  ↓
Repetir

Nice! 🔗😸

🌳 Maximum Depth of Binary Tree

Por fim, vamos olhar uma tree.

Imagine esta binary tree:

Qual é sua maximum depth?

O path mais longo da root até uma leaf possui três nodes:

Então a resposta é:

Como podemos calcular isso?

Pense em uma Tree Menor

Imagine que estamos em um único node.

Não precisamos entender a tree inteira de uma vez.

Só precisamos perguntar:

Qual é a depth da left subtree?

Qual é a depth da right subtree?

Depois escolhemos a maior.

E adicionamos 1 pelo node atual.

É exatamente isso que esta implementação faz:

function maxDepth(root: TreeNode | null): number {
  if (root === null) {
    return 0;
  }

  const leftDepth = maxDepth(root.left);
  const rightDepth = maxDepth(root.right);

  return Math.max(leftDepth, rightDepth) + 1;
}

A ideia mais importante é:

Math.max(leftDepth, rightDepth) + 1;

Mas recursion pode parecer meio estranha no começo.

Quando chamamos:

maxDepth(root.left);

onde fica a function que estava rodando antes?

E como todas essas chamadas de maxDepth acabam virando um único number?

Vamos acompanhar um example pequeno.

Começamos no:

Mas o node 1 ainda não consegue saber sua depth.

Primeiro ele pergunta ao left child:

maxDepth(2)

O node 2 pergunta ao 4:

maxDepth(4)

O node 4 não possui children.

Então os dois lados acabam chegando a:

null

maxDepth(null);

retorna:

Agora o node 4 consegue calcular:

max(0, 0) + 1
= 1

Depois voltamos ao node 2.

A left side possui depth:

A right side é null:

Então:

max(1, 0) + 1
= 2

Agora voltamos ao node 1.

Eventualmente, sua right subtree também retorna:

Então o node 1 recebe:

leftDepth = 2
rightDepth = 1

E calcula:

max(2, 1) + 1
= 3

Resposta:

🎉

A parte interessante: descer e depois voltar

Para mim, essa é uma das partes mais interessantes da recursion.

Primeiro, as function calls descem pela tree.

1
↓
2
↓
4
↓
null

Mas a resposta é construída enquanto voltamos.

null → 0
4    → 1
2    → 2
1    → 3

Então recursion não é apenas:

Continue chamando a mesma function.

Na verdade existem duas direções:

Descer
  ↓
Chegar ao base case
  ↓
Retornar os values para cima

O base case aqui é:

if (root === null) {
  return 0;
}

Sem ele, a recursion não teria onde parar.

Complexity

Cada node é visitado uma vez.

Time: O(n)

O tamanho da recursive call stack depende da height da tree.

Space: O(h)

onde h é a height da tree.

Em uma balanced tree, isso fica aproximadamente:

O(log n)

No pior caso, se a tree parecer uma linked list:

a depth pode chegar a:

O(n)

👀 Vamos visualizar

Recursion provavelmente é um dos meus examples favoritos para visualizar.

Porque a implementação final é minúscula:

const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);

return Math.max(leftDepth, rightDepth) + 1;

Mas muita coisa está escondida dentro dessas function calls.

Lendo apenas o code, às vezes parece:

maxDepth()
inside maxDepth()
inside maxDepth()
inside maxDepth()
...

Onde estamos agora??? 😿

https://dsa-view-view.vercel.app/#s=j.eyJlIjoidHJlZS1kZXB0aCIsImwiOiJ0eXBlc2NyaXB0IiwibSI6InZlcmlmaWNhdGlvbiIsInYiOjF9

Quando percorremos a execução step-by-step, conseguimos acompanhar as duas partes.

Primeiro, descemos:

Going down

1
↓
2
↓
4
↓
null

E depois voltamos:

Coming back

null → 0
↓
4 → 1
↓
2 → 2
↓
1 → 3

Assim, a ideia da recursion fica muito mais fácil de enxergar.

Pergunte a subproblems menores pelas respostas e use essas respostas para construir a resposta atual.

🌳😸

🧠 O que realmente aprendemos?

Esses três problemas parecem completamente diferentes.

Mas cada um apresenta uma forma muito útil de pensar.

Valid Parentheses

Use uma stack quando o item mais recente precisa ser processado primeiro.

Qual foi a última coisa que eu abri?

Reverse Linked List

Ao mudar references, salve o que ainda será necessário antes de quebrar a connection antiga.

Para onde eu preciso ir depois antes de mudar este pointer?

Maximum Depth of Binary Tree

Quebre um problema em versões menores do mesmo problema.

Posso obter as respostas dos meus children e construir minha resposta a partir delas?

Essa é uma das razões pelas quais gosto de aprender esses três problemas juntos.

As implementações não são muito grandes.

Mas cada uma apresenta um mental model completamente diferente:

Stack
Pointer
Recursion

E aprender esses mental models costuma ser muito mais difícil do que aprender a syntax.

Às vezes o code nos diz o que acontece.

Mas eu também quero ver como acontece.

Eu quero View View. 👀👀

🎯 Conclusão

Neste artigo, vimos:

Valid Parentheses com uma stack
Reverse Linked List com pointer manipulation
Maximum Depth of Binary Tree com recursion

E, mais importante, acompanhamos o state enquanto cada algoritmo estava rodando.

Vimos como a stack muda com:

stack.push() / stack.pop()

Vimos estes pointers atravessando uma linked list:

prev
current
next

E vimos recursive calls descendo por uma tree e devolvendo suas respostas enquanto voltavam.

Foi exatamente para ver esse tipo de coisa que criei o DSA View View.

https://dsa-view-view.vercel.app

Você pode escrever ou carregar uma implementação em TypeScript, executá-la com seus próprios inputs e avançar ou voltar pelo runtime.

Se você também está aprendendo DSA, experimente visualizar um desses problemas step-by-step.

Especialmente quando uma solution parece assim:

Eu entendo cada linha separadamente... mas, por algum motivo, ainda não entendo o todo. 😿

Ver o runtime pode ajudar a conectar essas peças.

E, se houver algum problema de DSA que você gostaria que eu abordasse no próximo artigo, me conta nos comentários!

Eu ainda tenho muitos algoritmos para aprender também. 😸

Vamos treinar nossos músculos de DSA juntos! 💪

Se você gostar do DSA View View, deixe uma star ⭐

https://github.com/nyaomaru/dsa-view-view

Até o próximo artigo!

🥞 Valid Parentheses

Vamos usar uma Stack

E quando é Invalid?

Complexity

👀 Vamos visualizar

🔗 Reverse Linked List

Três Variables Importantes

Step 1: Salvar o próximo Node

Step 2: Inverter a Seta

Step 3: Mover prev

Step 4: Mover current

Complexity

👀 Vamos visualizar

🌳 Maximum Depth of Binary Tree

Pense em uma Tree Menor

A parte interessante: descer e depois voltar

Complexity

👀 Vamos visualizar

🧠 O que realmente aprendemos?

Valid Parentheses

Reverse Linked List

Maximum Depth of Binary Tree

🎯 Conclusão

Step 3: Mover `prev`

Step 4: Mover `current`