Aprender DSA é chato? Vamos usar o DSA View View 👀👀 (Two Sum, Binary Search e Bubble Sort)
Oi oi!
Eu sou @nyaomaru, engenheiro frontend que não gosta muito de lugares cheios, então estou planejando tirar umas férias tranquilas em setembro. 🏝️
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.
Mas só apresentar a ferramenta não é suficiente.
Ela realmente ajuda a entender DSA?
Vamos testar!
Neste artigo, vamos passar por três problemas clássicos:
- Two Sum
- Binary Search
- Bubble Sort
Primeiro vamos entender o algoritmo e, depois, ver o que realmente acontece com o DSA View View.
Eu também ainda estou aprendendo DSA, então vamos aprender juntos! 😸
🗺️ Two Sum
Vamos começar com um problema bem famoso.
Dado um array de números e um valor target, precisamos encontrar os índices de dois números cuja soma seja igual ao target.
Por exemplo:
nums = [2, 7, 11, 15];
target = 9;
A resposta é:
[0, 1];
Porque:
2 + 7 = 9
Simples!
Então, como podemos encontrar esses dois números? 🤔
Brute Force
A abordagem mais simples provavelmente é verificar todos os pares possíveis.
function twoSum(nums: number[], target: number): number[] {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}
Isso funciona.
Mas, se o array ficar grande, talvez seja necessário comparar muitos pares, certo?
A complexidade de tempo é O(n²).
Será que podemos evitar verificar os mesmos valores várias vezes?
Sim.
Vamos usar um Map.
function twoSum(nums: number[], target: number): number[] {
const seen = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const current = nums[i];
const need = target - current;
if (seen.has(need)) {
return [seen.get(need)!, i];
}
seen.set(current, i);
}
return [];
}
A parte importante é esta 👇
const need = target - current;
Em vez de perguntar:
Quais dois números eu preciso combinar?
perguntamos:
Qual número eu preciso para completar o target?
Vamos acompanhar o exemplo.
No começo:
current = 2
target = 9
need = 9 - 2
= 7
Já vimos 7?
Não.
Então guardamos 2.
seen = {
2 → 0
}
Depois:
current = 7
target = 9
need = 9 - 7
= 2
Já vimos 2?
Sim! 👀👀
seen = {
2 → 0
}
Então:
return [0, 1];
Pronto!
Como precisamos percorrer o array apenas uma vez:
Time: O(n)
Space: O(n)
👀 Vamos visualizar
A implementação é pequena.
Mas, quando eu estava aprendendo esse pattern, esta parte ainda parecia um pouco mágica:
if (seen.has(need))
- De onde veio
need? - O que existe dentro de
seenneste momento? - Por que verificar os valores anteriores resolve o problema?
É exatamente aqui que a visualização ajuda.
Com o DSA View View, podemos avançar pelo runtime um step de cada vez e observar como os valores mudam.
2
↓
Need 7
↓
Remember 2
↓
7
↓
Need 2
↓
Found 2!
🎉
Agora o Map não parece mais algum truque misterioso.
Podemos realmente acompanhar a ideia:
Lembre o que já vimos e verifique se o valor de que precisamos está lá.
Nice! 😸
🔍 Binary Search
Agora vamos para Binary Search.
Imagine que temos este array ordenado:
[1, 3, 5, 7, 9, 11, 13]
E queremos encontrar:
11
Claro, poderíamos começar em 1 e verificar cada número.
1 → 3 → 5 → 7 → 9 → 11
Isso funciona.
Mas Binary Search faz algo mais esperto.
Em vez de verificar desde o começo, ele olha para o meio.
[1, 3, 5, 7, 9, 11, 13]
↑
mid
O valor do meio é 7.
Estamos procurando 11.
11 > 7
Como o array está ordenado, já sabemos algo muito útil.
Tudo à esquerda de 7 também é menor que 11.
Então não precisamos mais dessa metade. 👋
[1, 3, 5, 7, 9, 11, 13]
└───────┘
search
Agora verificamos o meio do range restante.
[9, 11, 13]
↑
mid
E:
11 === 11
Encontramos! 🎉
Aqui está a implementação:
function binarySearch(nums: number[], target: number): number {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
Temos três variáveis importantes:
left
right
mid
Elas representam o search range atual.
No nosso exemplo, começam assim:
left = 0
right = 6
mid = 3
[1, 3, 5, 7, 9, 11, 13]
↑ ↑ ↑
left mid right
Como:
nums[mid] < target;
movemos left.
left = mid + 1;
Agora:
[1, 3, 5, 7, 9, 11, 13]
↑ ↑ ↑
left mid right
E encontramos 11.
Por que Binary Search é rápido?
Essa é a parte interessante.
A cada step, removemos aproximadamente metade dos candidatos restantes.
Se houver 1.000 valores, não precisamos necessariamente fazer 1.000 verificações.
Fica aproximadamente assim:
1000
↓
500
↓
250
↓
125
↓
...
Por isso Binary Search possui:
Time: O(log n)
Space: O(1)
Mas existe uma condição muito importante.
Os dados precisam estar ordenados.
Sem dados ordenados, não podemos descartar metade do search range com segurança.
👀 Vamos visualizar
Binary Search é um dos algoritmos que me fizeram querer uma ferramenta de visualização desde o começo.
O code em si é curto:
left = mid + 1;
ou:
right = mid - 1;
Easy.
Mas, enquanto eu aprendia, às vezes pensava:
Espera... qual parte estamos procurando agora? 😿
Quando visualizamos left, mid e right, a ideia fica muito mais fácil de acompanhar.
Não estamos alterando três números aleatoriamente.
Estamos diminuindo continuamente o search range.
███████████████
↓
███████
↓
███
↓
█
Isso é Binary Search!
Corte a metade desnecessária.
Depois corte novamente.
E novamente.
E novamente.
Até encontrar a resposta. ✂️😸
🫧 Bubble Sort
Por fim, vamos ordenar alguma coisa!
Considere este array:
[5, 1, 4, 2, 8];
Queremos:
[1, 2, 4, 5, 8];
Bubble Sort compara repetidamente dois valores vizinhos.
Se eles estiverem na ordem errada, fazemos swap.
Vamos olhar o começo.
[5, 1, 4, 2, 8]
↑ ↑
Comparamos:
5 > 1
Então fazemos swap.
[1, 5, 4, 2, 8]
Próximo:
[1, 5, 4, 2, 8]
↑ ↑
De novo:
5 > 4
Swap!
[1, 4, 5, 2, 8]
E continuamos.
[1, 4, 5, 2, 8]
↑ ↑
5 > 2
Swap!
[1, 4, 2, 5, 8]
Eventualmente, os valores maiores vão se movendo para o final do array.
Eles meio que...
sobem como bolhas. 🫧
É por isso que se chama Bubble Sort.
Aqui está uma implementação simples:
function bubbleSort(nums: number[]): number[] {
for (let i = 0; i < nums.length - 1; i++) {
for (let j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
}
}
}
return nums;
}
Comparamos repetidamente:
nums[j];
e:
nums[j + 1];
e fazemos swap quando necessário.
Depois de um pass completo, o maior valor restante chega à posição correta perto do final.
Então, no próximo pass, não precisamos verificar essa posição novamente.
É por isso que o inner loop contém:
nums.length - i - 1;
Complexidade
Bubble Sort não é muito rápido para arrays grandes.
Sua complexidade é:
Time: O(n²)
Space: O(1)
Então provavelmente não vou começar a substituir o sorting de production por Bubble Sort amanhã. 😸
Mas, como exemplo de aprendizado, eu gosto muito dele.
Por quê?
Porque podemos ver o algoritmo funcionando.
👀 Vamos visualizar
Esse provavelmente é o mais satisfatório visualmente dos três.
Em vez de apenas ler:
[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
podemos acompanhar os valores se movendo pelo array.
[5, 1, 4, 2, 8]
↓ swap
[1, 5, 4, 2, 8]
↓ swap
[1, 4, 5, 2, 8]
↓ swap
[1, 4, 2, 5, 8]
Depois começa outro pass.
O code contém nested loops, indexes, comparisons e swaps.
Mas, visualmente, a regra básica é extremamente simples:
Compare os vizinhos. Se o valor da esquerda for maior, faça swap.
Repita.
Repita.
Repita.
Sorted! 🎉
🧠 O que realmente aprendemos?
Esses três problemas parecem bem diferentes.
Mas cada um apresenta uma forma útil de pensar.
Two Sum
Guarde informações dos steps anteriores.
Já vi o valor de que preciso?
Binary Search
Use o que já sabemos para remover candidatos impossíveis.
Posso descartar com segurança metade do search space?
Bubble Sort
Quebre um problema maior em várias comparações pequenas.
Esses dois valores estão na ordem correta?
Essa é uma das coisas que acho interessantes em aprender DSA.
No começo, a implementação pode parecer uma coleção de indexes, loops, conditions e variáveis misteriosas.
Mas, por trás do code, geralmente existe uma ideia muito mais simples.
E às vezes eu não entendo completamente essa ideia apenas olhando para o code.
Eu quero ver. 👀👀
🎯 Conclusão
Neste artigo, vimos três algoritmos clássicos:
- Two Sum com
Map - Binary Search
- Bubble Sort
E, mais importante, vimos como os dados mudam durante a execução.
Acho que é justamente aqui que a visualização pode ser especialmente útil.
- Ler a implementação final nos diz o que o code é.
- Percorrer a execução step-by-step ajuda a entender por que ele funciona.
Foi exatamente por isso 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, tente pegar um problema que já resolveu e visualizá-lo step-by-step.
Talvez você perceba algo que não tinha percebido apenas lendo o code. 👀
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!