Desenferrujando a lógica #02: Container With Most Water

Depois de resolver o primeiro exercício da série, continuei no LeetCode para trabalhar a lógica sem pedir uma solução pronta. O desafio 011 é o Container With Most Water.

Recebemos um array de alturas e precisamos escolher duas linhas que formem o recipiente com a maior área.

Como calcular a área

Se escolho as posições left e right, a largura é a distância entre elas. A altura do recipiente é limitada pela menor das duas linhas.

área = min(altura da esquerda, altura da direita) × distância

Por exemplo, com estas alturas:

[1, 8, 6, 2, 5, 4, 8, 3, 7]

As linhas nas posições 1 e 8 têm alturas 8 e 7. A menor altura é 7, e a distância entre elas é 7. Essa combinação produz uma área de 49.

Minha primeira tentativa

Comecei com dois ponteiros, um em cada ponta do array. Depois de calcular a área atual, eu simulava duas possibilidades:

• avançar o ponteiro da esquerda;
• recuar o ponteiro da direita.

Eu calculava a área dos dois próximos pares e escolhia o maior. O trecho principal era este:

const paddingLeftArea =
  Math.min(heights[leftIndex + 1], heights[rigthIndex]) *
  (rigthIndex - leftIndex + 1);

const paddingRightArea =
  Math.min(heights[leftIndex], heights[rigthIndex - 1]) *
  (rigthIndex - 1 - leftIndex);

if (paddingLeftArea > paddingRightArea && paddingLeftArea > maxArea) {
  leftIndex += 1;
} else {
  rigthIndex -= 1;
}

O problema estava na hipótese. A melhor decisão local não garante a melhor área no restante do array. Eu tentava adivinhar o caminho olhando apenas para os dois próximos movimentos. Também havia um erro na fórmula da distância desse rascunho: para um par de posições, a largura é right - left.

A observação que destrava o problema

A área depende de duas coisas: largura e menor altura.

Quando os ponteiros estão nas posições left e right, mover o ponteiro da maior altura não pode aumentar a altura mínima do recipiente. A largura sempre diminui, e a altura que limita a área continua presente.

Por isso, o ponteiro que deve avançar é o da menor altura. É o único movimento que pode encontrar uma linha mais alta e compensar a perda de largura.

Se as alturas forem iguais, qualquer um dos dois pode avançar. No código, escolhi avançar o da esquerda quando heights[leftIndex] <= heights[rigthIndex].

Solução com dois ponteiros

/**
 * @param {number[]} heights
 * @return {number}
 */
var maxArea = function (heights) {
  let leftIndex = 0;
  let rigthIndex = heights.length - 1;
  let maxArea = 0;

  while (leftIndex < rigthIndex) {
    const minH = Math.min(heights[leftIndex], heights[rigthIndex]);
    const currentArea = minH * (rigthIndex - leftIndex);

    maxArea = Math.max(maxArea, currentArea);

    if (heights[leftIndex] <= heights[rigthIndex]) {
      leftIndex++;
    } else {
      rigthIndex--;
    }
  }

  return maxArea;
};

A cada rodada, calculo a área do par atual, atualizo a maior área encontrada e movo um dos ponteiros. O while se aproxima do centro e termina.

O detalhe do avanço importa. Na versão que eu havia escrito, os ponteiros só avançavam quando a área atual não era maior que maxArea. Se uma nova área máxima fosse encontrada, a mesma combinação seria calculada de novo, sem sair do loop. A correção foi separar as duas decisões: registrar a área e, depois, mover o ponteiro da menor altura.

O resultado das tentativas

O histórico do LeetCode ficou assim:

• JavaScript: aceita, 3 ms e 63.6 MB.
• JavaScript: resposta incorreta.
• JavaScript: resposta incorreta.
• Go: aceita, 0 ms e 9.6 MB.
• TypeScript: aceita, 3 ms e 63.9 MB.
• Go: resposta incorreta.

Foram três tentativas com resposta incorreta antes de chegar às soluções aceitas em JavaScript, Go e TypeScript. Mais do que contar submissões, eu queria olhar para o erro, entender a hipótese que falhou e tentar de novo sem terceirizar todo o raciocínio.

Complexidade

O algoritmo percorre o array uma vez. Em cada iteração, um dos ponteiros avança, então a complexidade de tempo é O(n) e a complexidade de espaço é O(1).

A primeira tentativa também usava dois ponteiros, mas fazia trabalho extra para comparar possibilidades futuras. A segunda solução usa uma propriedade do problema para descartar com segurança parte das combinações.

Esse foi o exercício desta vez: não confundir uma escolha que parece boa agora com uma decisão que o problema realmente permite justificar.

---

Série Desenferrujando a lógica #02 — Container With Most Water. Problema em leetcode.com/problems/container-with-most-water.