Padrão 2: Two Pointers

Dois índices que se movem com inteligência. O segredo do padrão não são os ponteiros — é o argumento que permite descartar candidatos em bloco sem nem olhar para eles.

🎯

Tente primeiro: Container With Most Water

Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.

Cada posição é uma parede de altura heights[i]. Escolha duas paredes que, com o eixo x, formem o recipiente com mais água. A água é limitada pela parede mais baixa: área = (j - i) × min(heights[i], heights[j]).

Exemplo: heights = [1, 8, 6, 2, 5, 4, 8, 3, 7] → 49.

Carregando editor…

Tentou? A força bruta testa todos os pares de paredes — O(n²) — e funciona nos exemplos pequenos, mas seria lenta demais para entradas grandes. O incômodo: muitos desses pares obviamente não podem ser a resposta. A teoria abaixo mostra como descartá-los em bloco.

A teoria: que problema o two pointers resolve?

Muitos problemas pedem o melhor par (ou trio) de elementos: o par que soma o alvo, o par que forma o maior recipiente, o trio que soma zero. A força bruta testa todos os pares: O(n²).

O two pointers ataca o desperdício central dessa força bruta: ela testa pares que não têm nenhuma chance de ser a resposta. Se o array tem alguma estrutura — está ordenado, ou a qualidade do par depende do menor lado — dá para provar que blocos inteiros de pares são inúteis e pulá-los de uma vez.

A mecânica clássica (ponteiros convergentes)

left  = início do array
right = fim do array
enquanto left < right:
    avalie o par (left, right)
    decida QUAL ponteiro mover — e o movimento descarta
    todos os pares que envolviam a posição abandonada

Cada passo elimina uma posição inteira (e todos os pares com ela). São n posições, então o loop roda no máximo n vezes: O(n). A mágica está na decisão de qual ponteiro mover — e ela exige uma justificativa.

O exemplo perfeito: par que soma o alvo, em array ORDENADO

Array ordenado, procuro dois números que somam alvo:

Se nums[left] + nums[right] é menor que o alvo → a soma precisa crescer. Mover right para a esquerda só diminui a soma. Logo, o único movimento útil é left += 1. E mais: acabamos de provar que nums[left] não forma par com ninguém (até o maior elemento foi pouco) — descartamos n pares de uma vez.
Se a soma é maior → simétrico: right -= 1.

Esse é o coração do padrão: cada movimento vem com uma prova de descarte. Sem a prova, two pointers é chute.

Os sinais no enunciado

O array está ordenado (ou ordenar não estraga a resposta).
A pergunta envolve pares/trios com alguma condição de soma, distância ou tamanho.
Dá para raciocinar: "se o par atual falha por excesso, mover o ponteiro X não ajuda".
Pedem O(1) de espaço (hash map gastaria O(n)).

Exemplo 1 — Container With Most Water

"Cada posição é uma parede de altura heights[i]. Escolha duas paredes que formem o recipiente com mais água." A água é limitada pela parede menor: área = (right - left) × min(altura_left, altura_right).

Força bruta: todas as combinações de paredes — O(n²).
O desperdício: se a parede da esquerda é a menor, qualquer outro par com ela e uma parede mais próxima é pior: a largura encolhe e a altura continua travada pela mesma parede menor. Todos esses pares são inúteis.
O padrão: comece com o recipiente mais largo (pontas) e, a cada passo, abandone a parede menor — é a única esperança de achar algo melhor.

Veja a regra de decisão funcionando (repare: o ponteiro que se move é sempre o da barra mais baixa):

Execução real, gravada passo a passo

Carregando Python no navegador (primeira vez demora alguns segundos)…

Por que é O(n)?

A cada volta do loop, left sobe ou right desce — os ponteiros só andam um em direção ao outro e nunca voltam. Eles se cruzam depois de no máximo n-1 movimentos, e cada volta faz só trabalho O(1) (comparações e aritmética). Total: O(n) de tempo, O(1) de espaço — nem memória extra este padrão pede.

Solução	Tempo	Espaço	Por quê
Força bruta	O(n²)	O(1)	todos os pares de paredes
Two pointers	O(n)	O(1)	cada passo descarta uma parede para sempre

Exemplo 2 — 3Sum (o padrão composto)

"Encontre todos os trios que somam zero, sem repetir trios." Parece outro universo, mas é o problema do "par que soma o alvo" usado como peça:

Ordene o array — O(n log n). (Agora two pointers fica disponível!)
Fixe o primeiro número nums[i] — um loop O(n).
O resto virou: "no trecho ordenado à direita de i, ache pares que somam -nums[i]" — exatamente o exemplo da teoria, O(n) com dois ponteiros.
Pule valores repetidos ao avançar (para não duplicar trios).

Por que é O(n²)?

Loop de fora O(n) × varredura de ponteiros O(n) = O(n²); o sort O(n log n) fica menor e some na soma (regra 1 dos fundamentos). Para um problema que tem O(n³) de força bruta, O(n²) com espaço O(1) é o estado da arte.

Carregando editor…

Hash map ou two pointers? (os dois resolvem pares!)

Situação	Melhor escolha	Por quê
Array sem ordem, preciso dos índices originais	Hash map	ordenar destruiria os índices
Array já ordenado (ou posso ordenar)	Two pointers	O(1) de espaço, sem custo de hash
Pares com condição de desigualdade (soma < alvo, distância ≤ k)	Two pointers	hash map só acha valores exatos
Espaço O(1) exigido	Two pointers	hash map paga O(n)

🧠 Quiz de fixação

0/4

1. No Container With Most Water, por que mover sempre o ponteiro da parede MENOR?

2. Por que two pointers convergentes garante O(n) e não O(n²)?

3. No 3Sum, qual é a divisão de trabalho que leva a O(n²)?

4. Enunciado novo: 'num array ordenado, conte os pares com soma MENOR que k'. Hash map ou two pointers — e por quê?

Resumo

Two pointers = descarte provado de candidatos em bloco; a prova de cada movimento é obrigatória.
Convergentes: O(n) porque o progresso é irreversível — cada passo consome uma posição.
Custa O(1) de espaço — vantagem sobre o hash map quando o array é ordenado ou a condição é desigualdade.
Problemas de trio = fixe um + two pointers no resto (3Sum, O(n²)).

Próxima aula: quando a pergunta é sobre trechos contíguos do array — sliding window.

Todas as aulas da seção