Two pointers e sliding window

O problema

Tem técnica de entrevista que assusta mais pelo nome do que pela lógica.

Two pointers e sliding window entram muito nessa categoria.

Muita gente trata isso como receita decorada:

• se a pergunta parece substring, usa sliding window
• se parece array ordenado, usa two pointers

Isso até ajuda no começo.

Mas quebra rápido quando a pergunta muda um detalhe.

O problema real não é faltar nome.

É falta de modelo mental para entender por que mover fronteiras funciona.

Modelo mental

Essas técnicas existem para evitar trabalho repetido.

Você tem uma sequência.

E, em vez de reavaliar vários trechos do zero, vai ajustando limites e reaproveitando o que já sabe.

No fundo, o raciocínio é este:

• existe uma região ativa da sequência
• eu consigo expandir ou contrair essa região
• cada movimento muda o estado de forma previsível

Se quiser resumir em uma frase:

Two pointers e sliding window funcionam quando a resposta está em mover fronteiras, não em recomeçar a análise toda vez.

Two pointers é a ideia mais geral.

Sliding window é um caso específico em que a região ativa costuma ser um trecho contíguo definido por dois limites.

Quebrando o problema

Quando two pointers costuma aparecer

Normalmente em problemas como:

• array ordenado
• comparação entre extremidades
• encontrar par com alguma propriedade
• decidir qual lado avançar com base no valor atual

Exemplos típicos:

• soma alvo em array ordenado
• remover duplicados em array ordenado
• container com mais água
• palíndromo com comparação de bordas

A ideia é que os ponteiros carregam informação suficiente para a próxima decisão.

Quando sliding window costuma aparecer

Sliding window costuma aparecer quando o problema fala de:

• substring
• subarray
• trecho contíguo
• maior ou menor janela que satisfaz condição

Exemplos clássicos:

• maior substring sem repetição
• menor subarray com soma maior que alvo
• janela com no máximo k trocas

O ponto central é que a janela guarda um estado que pode ser atualizado incrementalmente:

• soma
• frequência
• quantidade de duplicados
• número de caracteres válidos

A pergunta que destrava

Quando bater a dúvida, pergunte:

Eu consigo mover um limite e atualizar o estado sem recalcular tudo?

Se sim, sliding window começa a fazer sentido.

Outra pergunta útil:

Existe uma regra clara para decidir qual ponteiro move agora?

Se sim, two pointers pode estar no caminho certo.

Nem toda janela é deslizante de verdade

Às vezes a pessoa força a técnica só porque viu a palavra substring no enunciado.

Mas a condição não fecha incrementalmente.

Ou a propriedade depende de informação que não pode ser mantida de forma barata.

Quando isso acontece, tentar enfiar sliding window à força só cria código confuso.

Esse é um bom teste de maturidade:

se manter o estado começa a ficar forçado demais, talvez a técnica não seja a certa.

Exemplo simples

Pegue a pergunta:

Encontrar a maior substring sem caracteres repetidos.

Baseline

Testar todas as substrings possíveis.

Para cada uma, verificar se há repetição.

Funciona.

Mas custa caro demais.

Sliding window

Você mantém:

• left
• right
• um Set ou mapa com os caracteres presentes

Enquanto expande right, vai adicionando o caractere atual.

Se aparecer repetição, move left até a janela voltar a ficar válida.

O ponto importante é este:

você não recalcula a substring inteira.

Você só ajusta os limites e atualiza o estado.

É isso que derruba o custo.

O padrão não é “decore a solução desse problema”.

É:

• trecho contíguo
• condição de validade da janela
• atualização incremental do estado

Erros comuns

• Usar two pointers sem conseguir justificar por que um ponteiro anda e o outro não.
• Forçar sliding window em problema que não depende de trecho contíguo.
• Recalcular a janela inteira a cada passo e perder a vantagem da técnica.
• Confundir array ordenado com janela contígua e misturar ideias.
• Tratar o nome da técnica como objetivo final em vez de entender a estrutura do problema.

Como um senior pensa

Quem já viu bastante problema desse tipo tende a procurar invariantes.

O raciocínio é algo como:

• o que minha janela ou meus ponteiros representam agora?
• em que condição esse estado é válido?
• o que muda quando avanço um lado?
• consigo garantir que cada elemento entra e sai poucas vezes?

Essa última pergunta é importante.

Ela costuma explicar por que muitas dessas soluções viram O(n).

Cada item não fica sendo reprocessado o tempo todo.

Ele entra na janela, talvez saia, e a análise segue.

No trabalho real, esse jeito de pensar aparece em stream, parsing, métricas em janela, deduplicação temporal e muita lógica de produto.

Então vale mais do que para entrevista.

O que o entrevistador quer ver

Ele quer entender se você:

• reconhece o formato de trecho contíguo ou comparação de fronteiras
• sabe definir o estado mantido
• consegue explicar a regra de movimento dos ponteiros
• entende por que isso reduz complexidade

Se a sua explicação for “eu mantenho a janela válida, expando enquanto posso e contraio quando quebro a regra”, isso já mostra critério.

A técnica não é sobre dois ponteiros. É sobre duas decisões bem justificadas.

Quando a fronteira certa se move na hora certa, o problema para de exigir força bruta.