Aprenda Trapping Rain Water, Top K Frequent e Selection Sort com visualização passo a passo no DSA View View 👀👀 · nyaomaru

Oi oi!

Eu sou @nyaomaru, engenheiro frontend que ultimamente ficou completamente obcecado por ramen. 😸🍜

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 implementation realmente roda.

Nos artigos anteriores, vimos problemas como:

Two Sum
Binary Search
Bubble Sort
Valid Parentheses
Reverse Linked List
Maximum Depth of Binary Tree
Number of Islands
Invert Binary Tree
Course Schedule

Desta vez, vamos tentar mais três:

Trapping Rain Water
Top K Frequent Elements
Selection Sort

Esses três problemas apresentam formas de pensar bem diferentes:

Reduzir o problema pelos dois lados

Primeiro contar, depois organizar por frequency

Selecionar repetidamente o próximo value

Mais uma vez, as implementations não são necessariamente enormes.

Mas existem vários values mudando ao mesmo tempo, e precisamos manter tudo isso na cabeça.

Então, em vez de apenas ler o final code...

Vamos ver o que realmente acontece. 👀👀

🌧️ Trapping Rain Water

Vamos começar com Trapping Rain Water.

Suponha que temos estas alturas:

[0, 1, 0, 2, 1, 0, 1, 3]

Se desenharmos como walls, fica mais ou menos assim:

              █
      █       █
  █   █ █   █ █
-----------------
0 1 0 2 1 0 1 3

A chuva cai de cima.

Parte da água escapa.

Mas parte fica presa entre walls mais altos.

Por exemplo:

      █~~~~~~~█
  █~~~█~~~~~~~█
-----------------

Então a pergunta é:

Quanta água pode ficar presa?

No começo, eu achei esse problema bem confuso. 😿

Porque a quantidade de água acima de uma position depende de walls que estão em outros lugares.

Então, de que informação realmente precisamos?

Quanto de água cabe acima de uma Position?

Imagine esta position:

left wall     right wall
    █             █
    █      x      █
    █      █      █

O water level não pode ficar mais alto que o lado menor.

Então o maior nível possível é:

Math.min(leftMax, rightMax);

Depois subtraímos a altura atual.

Conceitualmente:

water = min(leftMax, rightMax) - currentHeight

Essa é a ideia básica.

Mas será que precisamos calcular os dois lados de novo para cada position?

Não.

Podemos usar two pointers.

Two Pointers

A implementation é esta:

function trap(height: number[]): number {
  let left = 0;
  let right = height.length - 1;

  let leftMax = 0;
  let rightMax = 0;

  let water = 0;

  while (left <= right) {
    if (height[left] <= height[right]) {
      if (height[left] >= leftMax) {
        leftMax = height[left];
      } else {
        water += leftMax - height[left];
      }

      left++;
    } else {
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        water += rightMax - height[right];
      }

      right--;
    }
  }

  return water;
}

Existem vários values importantes:

left
right
leftMax
rightMax
water

Esse é exatamente o tipo de code em que eu entendo cada variable individualmente...

mas começo a me perder quando todos mudam juntos. 😹

Vamos acompanhar um example menor:

[2, 0, 1, 3]

Começando pelos dois lados

No início:

left = 0
right = 3

[2, 0, 1, 3]
 ↑        ↑
left    right

As alturas são:

height[left]  = 2
height[right] = 3

Como:

2 <= 3

processamos o lado esquerdo.

Existe uma wall de altura 2.

Então:

leftMax = 2

Depois movemos left.

[2, 0, 1, 3]
    ↑     ↑
   left right

Agora podemos prender água

A altura atual é:

Mas já sabemos que existe uma wall de altura 2 do lado esquerdo.

E o lado direito, neste momento, é pelo menos tão alto quanto essa wall.

Então esta position pode armazenar:

leftMax - height[left]
= 2

Logo:

water = 2

Movemos novamente.

[2, 0, 1, 3]
       ↑  ↑
      left right

Agora:

height[left] = 1
leftMax = 2

Então:

2 - 1 = 1

Mais uma unidade de água.

water = 3

Eventualmente chegamos à última wall.

Done! 🎉

Por que podemos processar o lado menor?

Essa é a parte importante.

Suponha:

height[left] <= height[right]

Nesse momento, já sabemos que existe uma wall à direita pelo menos tão alta quanto a wall atual do lado esquerdo.

Então, para a current left position, o fator limitante é a melhor wall que já encontramos pela esquerda.

Por isso podemos calcular com segurança:

leftMax - height[left];

sem precisar conhecer todas as future walls.

A mesma lógica funciona do outro lado.

Se:

height[right] < height[left]

processamos o lado direito usando rightMax.

Então o algorithm vai reduzindo a área desconhecida:

L → → →     ← ← ← R

até tudo ser processado.

Complexity

Cada pointer atravessa o array apenas uma vez.

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

👀 Vamos View View

Esse problema é um ótimo exemplo de por que gosto de visualization.

O code possui:

left
right
leftMax
rightMax
water

E todos eles mudam em momentos diferentes.

Quando eu leio apenas:

water += leftMax - height[left];

posso começar a perguntar:

Por que estamos usando leftMax aqui?
Quanto vale rightMax agora?
Por que movemos left em vez de right?
Quanta water já contamos?
Qual parte do array ainda não foi processada?

😿

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

Step-by-step, conseguimos ver a área de busca realmente diminuindo.

L         R
↓         ↓
[2, 0, 1, 3]

    L     R
    ↓     ↓
[2, 0, 1, 3]

       L  R
       ↓  ↓
[2, 0, 1, 3]

Ao mesmo tempo:

leftMax
rightMax
water

continuam mudando.

Na prática, o algorithm está perguntando:

Qual lado eu já consigo resolver com segurança agora?

Depois resolve esse lado e anda para dentro. 🌧️😸

🔢 Top K Frequent Elements

Agora vamos encontrar os Top K Frequent Elements.

Suponha que temos:

[1, 1, 1, 2, 2, 3]

k = 2

Quantas vezes cada number aparece?

1 → 3 vezes
2 → 2 vezes
3 → 1 vez

Então os dois values mais frequentes são:

[1, 2]

Até aqui, simples.

Mas como implementar?

Primeiro, conte tudo

A primeira coisa que precisamos é da frequency.

Podemos usar um Map.

const frequency = new Map<number, number>();

Depois contamos cada value.

for (const num of nums) {
  frequency.set(num, (frequency.get(num) ?? 0) + 1);
}

Para:

[1, 1, 1, 2, 2, 3]

obtemos:

frequency = {
  1 → 3
  2 → 2
  3 → 1
}

Nice.

Mas ainda precisamos do top K.

Claro, poderíamos ordenar tudo por frequency.

Mas existe outra abordagem interessante.

Use Frequency como Index

A maior frequency possível é:

nums.length

Então podemos criar buckets.

const buckets: number[][] = Array.from(
  { length: nums.length + 1 },
  () => []
);

O próprio index representa a frequency.

Por exemplo:

bucket[1] = values que aparecem 1 vez
bucket[2] = values que aparecem 2 vezes
bucket[3] = values que aparecem 3 vezes

No nosso example:

frequency = {
  1 → 3
  2 → 2
  3 → 1
}

os buckets ficam:

index 0 → []
index 1 → [3]
index 2 → [2]
index 3 → [1]

Isso é bem interessante. 👀👀

Em vez de perguntar:

Qual é a frequency deste number?

invertemos a relação:

Quais numbers possuem esta frequency?

Implementation

A implementation completa fica assim:

function topKFrequent(nums: number[], k: number): number[] {
  const frequency = new Map<number, number>();

  for (const num of nums) {
    frequency.set(num, (frequency.get(num) ?? 0) + 1);
  }

  const buckets: number[][] = Array.from(
    { length: nums.length + 1 },
    () => []
  );

  for (const [num, count] of frequency) {
    buckets[count].push(num);
  }

  const result: number[] = [];

  for (let count = buckets.length - 1; count >= 0; count--) {
    for (const num of buckets[count]) {
      result.push(num);

      if (result.length === k) {
        return result;
      }
    }
  }

  return result;
}

Vamos acompanhar.

Step 1: Construir o Frequency Map

Começamos com:

frequency = {}

Lemos o primeiro 1.

Depois outro.

1 → 1
1 → 2
1 → 3

Depois vem 2.

E outro 2.

1 → 3
2 → 1
2 → 2

Finalmente 3.

1 → 3
2 → 2
3 → 1

Done.

Step 2: Colocar os Values nos Buckets

Agora:

buckets[count].push(num);

Para:

1 → 3

fazemos:

buckets[3].push(1)

Para:

2 → 2

fazemos:

buckets[2].push(2)

3 → 1

vira:

buckets[1].push(3)

Então:

0: []
1: [3]
2: [2]
3: [1]

Step 3: Ler da maior Frequency

Queremos os values mais frequentes.

Então não começamos do 0.

Começamos do final.

3 → [1]
2 → [2]
1 → [3]

Pegamos 1.

result = [1]

Ainda falta mais um.

Descemos.

Pegamos 2.

result = [1, 2]

Agora:

result.length === k

Então retornamos.

Done! 🎉

Por que isso é interessante?

Eu gosto dessa solution porque a segunda data structure muda completamente a forma como olhamos a informação.

O Map diz:

value → frequency

Os buckets dizem:

frequency → values

Mesma informação.

Direção diferente.

E, de repente, encontrar os values mais frequentes fica muito simples.

Só precisamos andar de trás para frente pelos buckets.

Complexity

Contamos cada number uma vez.

Distribuímos cada unique number em um bucket.

Depois percorremos os buckets.

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

👀 Vamos View View

Aqui os dados mudam de formato várias vezes.

Primeiro:

nums
 ↓
frequency Map

Depois:

frequency Map
 ↓
buckets

E então:

buckets
 ↓
result

Quando lemos apenas a final implementation, pode ser fácil perder o motivo de criarmos duas data structures diferentes.

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

Com o runtime visível, podemos acompanhar os dados mudando de forma.

[1, 1, 1, 2, 2, 3]

        ↓ count

1 → 3
2 → 2
3 → 1

        ↓ bucket

1: [3]
2: [2]
3: [1]

        ↓ highest first

[1, 2]

Essa é a parte que eu gosto.

Nós não encontramos o top K por mágica.

Reorganizamos a informação até a resposta ficar fácil de ler. 🔢😸

👉 Selection Sort

Por fim, vamos ordenar alguma coisa de novo!

Já vimos Bubble Sort em um artigo anterior.

Desta vez, vamos tentar Selection Sort.

Suponha:

[5, 3, 4, 1, 2]

Queremos:

[1, 2, 3, 4, 5]

Selection Sort segue uma ideia bem simples:

Encontre o menor value restante e mova para a frente.

Depois repita.

First Pass

Começamos:

[5, 3, 4, 1, 2]
 ↑
 i

Assumimos que o primeiro value é, por enquanto, o menor.

minIndex = 0

Depois fazemos scan de tudo à direita.

5 vs 3

3 é menor.

Então:

minIndex = 1

Depois:

3 vs 4

Nada muda.

Depois:

3 vs 1

1 é menor.

minIndex = 3

Finalmente:

1 vs 2

Ainda é 1.

Então o menor value está no index 3.

Swap:

[5, 3, 4, 1, 2]
 ↑        ↑
 i       min

↓

[1, 3, 4, 5, 2]

Agora a primeira position está pronta.

[1 | 3, 4, 5, 2]
 ↑
sorted

Repeat

Agora começamos no index 1.

[1 | 3, 4, 5, 2]
     ↑
     i

Procuramos o menor value em:

[3, 4, 5, 2]

É 2.

Swap.

[1, 2 | 4, 5, 3]

De novo.

Encontre o menor value restante.

Eventualmente:

[1, 2, 3, 4, 5]

Sorted! 🎉

Implementation

function selectionSort(nums: number[]): number[] {
  for (let i = 0; i < nums.length - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[minIndex]) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
    }
  }

  return nums;
}

Existem dois indexes importantes:

i
minIndex

E também:

que procura dentro da área ainda unsorted.

Por que se chama Selection Sort?

Porque em cada pass selecionamos o menor value restante.

Encontrar o menor
  ↓
Selecioná-lo
  ↓
Mover para a frente
  ↓
Repetir

Esse é basicamente o algorithm inteiro.

Complexity

Para cada position, procuramos entre os values restantes.

Então:

Time: O(n²)

O array é ordenado in place.

Space: O(1)

Selection Sort não é algo que eu escolheria normalmente para ordenar um huge production dataset. 😹

Mas, como learning algorithm, ele é maravilhosamente visual.

👀 Vamos View View

A implementation tem nested loops.

for (let i = 0; i < nums.length - 1; i++) {
  let minIndex = i;

  for (let j = i + 1; j < nums.length; j++) {

Lendo o code, eu posso facilmente perder:

Qual área já está sorted?
Onde está i?
Onde está j?
Para onde minIndex aponta agora?
Em que momento exatamente o swap acontece?

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

Quando visualizamos, o pattern básico fica óbvio.

[5, 3, 4, 1, 2]
          ↑
       smallest

[1 | 3, 4, 5, 2]
               ↑
            smallest

[1, 2 | 4, 5, 3]

O algorithm vai aumentando continuamente uma área finalizada da esquerda para a direita.

Isso é Selection Sort.

Escolha o menor value restante.

Coloque-o na próxima position.

E repita. 🍥😸

🧠 O que realmente aprendemos?

Novamente, esses três problemas parecem completamente diferentes.

Mas cada um apresenta uma forma útil de pensar.

Trapping Rain Water

Use informação dos dois lados para decidir qual parte já pode ser resolvida com segurança.

De qual lado eu já sei o suficiente agora?

Top K Frequent Elements

Às vezes contar os dados é apenas o primeiro passo.

Reorganize a informação em uma estrutura onde a resposta fique fácil de obter.

Posso reorganizar esta informação em torno do que realmente preciso?

Selection Sort

Construa a resposta uma position definitiva de cada vez.

Qual value deve ocupar esta position agora?

Então, desta vez vimos:

Two pointers
Frequency buckets
Selection

Três mental models diferentes de novo.

E, assim como nos problemas anteriores, a parte difícil muitas vezes não é a syntax.

É o changing state.

Qual pointer se moveu?

Qual é o maximum agora?

O que existe dentro do Map?

Qual bucket mudou?

Onde está minIndex?

Qual parte já está pronta?

É coisa demais para manter na cabeça.

Então, em vez disso, eu quero ver. 👀👀

🎯 Conclusão

Neste artigo, vimos:

Trapping Rain Water com two pointers
Top K Frequent Elements com frequency buckets
Selection Sort

E, mais importante, acompanhamos como o state muda enquanto cada algorithm roda.

No Trapping Rain Water, vimos dois pointers avançando para dentro enquanto leftMax, rightMax e water mudavam.

left →       ← right

No Top K Frequent Elements, vimos os mesmos dados mudarem de representation.

array
  ↓
frequency Map
  ↓
buckets
  ↓
result

No Selection Sort, vimos a área sorted crescer uma position de cada vez.

É 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 TypeScript implementation, rodar com seus próprios inputs e navegar backward / forward pelo runtime.

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

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 algorithms 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!