No universo da programação e otimização de algoritmos, a técnica de ponteiros duplos (ou "two-pointers") é uma ferramenta poderosa e amplamente utilizada. Ela consiste em empregar dois índices ou ponteiros para percorrer uma estrutura de dados, geralmente um array ou lista encadeada, seja na mesma direção ou em direções opostas, com o objetivo de realizar operações eficientes.

Variantes Comuns de Ponteiros Duplos

• Ponteiros de Velocidade Diferenciada (ou Rápido/Lento): Estes ponteiros iniciam do mesmo ponto ou de pontos próximos e movem-se na mesma direção, mas com passos ou condições de avanço distintas.
  • Cenários típicos: Remoção de duplicatas em arrays ordenados, detecção de ciclos em listas encadeadas (algoritmo do "coelho e tartaruga"), e o problema de "mover zeros".
• Ponteiros Convergentes (ou Colidindo): Neste padrão, um ponteiro começa no início da estrutura (esquerda) e outro no final (direita), movendo-se em direção ao centro.
  • Cenários típicos: Busca binária, encontrar pares ou trios que somam a um alvo em arrays ordenados, inversão de strings, e verificação de palíndromos.

Por Que Utilizar Ponteiros Duplos?

A principal razão para a popularidade dos ponteiros duplos reside em seus benefícios significativos:

1. Otimização da Complexidade de Tempo: Frequentemente, essa abordagem consegue transformar algoritmos que exigiriam loops aninhados (complexidade O(N²)) em soluções lineares (complexidade O(N)), ao evitar varreduras desnecessárias ou repetitivas.
2. Eficiência de Espaço: Geralmente, os algoritmos de ponteiros duplos operam "in-place", ou seja, modificam a estrutura de dados original sem a necessidade de alocar espaço auxiliar significativo, resultando em uma complexidade de espaço de O(1).

Compreendendo esses fundamentos, vamos aplicar essa técnica ao problema clássico de "Mover Zeros".

O Problema: Mover Zeros (LeetCode 283)

O desafio é reorganizar um array de números inteiros, movendo todos os elementos zero para o final, mantendo a ordem relativa dos elementos não-zero. Por exemplo, dado [0, 1, 0, 3, 12], o resultado esperado é [1, 3, 12, 0, 0].

A abordagem ingênua de remover um zero e inserir outro no final resultaria em uma alta complexidade devido ao rearranjo contínuo dos elementos. A solução eficiente emprega ponteiros duplos para realizar a operação em uma única passagem.

Estratégia de Ponteiros

Imagine o array como uma sequência de caixas. Precisamos consolidar todas as caixas com itens (números não-zero) à esquerda e deixar as caixas vazias (zeros) à direita. Usaremos dois "manipuladores":

• Manipulador de Escrita (idxParaPreencher): Este ponteiro indica a próxima posição disponível para um elemento não-zero. Ele só avança quando um elemento não-zero é efetivamente colocado em sua posição.
• Manipulador de Leitura (idxAtual): Este ponteiro varre o array da esquerda para a direita, buscando por elementos não-zero.

Processo Ilustrativo: \[0, 1, 0, 3, 12\]

Vamos visualizar o funcionamento passo a passo:

Estado Inicial: Ambos os ponteiros começam no índice 0.

Array: [0, 1, 0, 3, 12]
        ^
       idxParaPreencher
       idxAtual

Passo 1: idxAtual encontra 0

• nums\[idxAtual\] é 0. O manipulador de escrita (idxParaPreencher) não age, pois espera um não-zero.
• idxAtual avança.

Array: [0, 1, 0, 3, 12]
        ^  ^
       idxParaPreencher
          idxAtual

Passo 2: idxAtual encontra 1 (Não-Zero)

• nums\[idxAtual\] é 1. Este é um não-zero.
• Ação: Copiamos nums\[idxAtual\] (que é 1) para nums\[idxParaPreencher\] (que é nums\[0\]).
• idxParaPreencher avança (pois preencheu uma posição válida).
• idxAtual avança.

Array: [1, 1, 0, 3, 12] (Após cópia: nums[0] = nums[1])
           ^  ^
          idxParaPreencher
             idxAtual

Passo 3: idxAtual encontra 0

• nums\[idxAtual\] é 0.
• idxAtual avança. idxParaPreencher permanece.

Array: [1, 1, 0, 3, 12]
           ^     ^
          idxParaPreencher
                idxAtual

Passo 4: idxAtual encontra 3 (Não-Zero)

• nums\[idxAtual\] é 3.
• Ação: Copiamos nums\[idxAtual\] (que é 3) para nums\[idxParaPreencher\] (que é nums\[1\]).
• idxParaPreencher avança.
• idxAtual avança.

Array: [1, 3, 0, 3, 12] (Após cópia: nums[1] = nums[3])
              ^  ^
             idxParaPreencher
                idxAtual

Passo 5: idxAtual encontra 12 (Não-Zero)

• nums\[idxAtual\] é 12.
• Ação: Copiamos nums\[idxAtual\] (que é 12) para nums\[idxParaPreencher\] (que é nums\[2\]).
• idxParaPreencher avança.
• idxAtual avança e atinge o fim do array, encerrando o loop principal.

Array: [1, 3, 12, 3, 12] (Após cópia: nums[2] = nums[4])
                   ^     ^ (Fim da iteração)
                  idxParaPreencher
                        idxAtual

Passo 6: Preenchimento Final

• Neste ponto, todos os não-zeros estão no início do array, em suas ordens relativas corretas. O idxParaPreencher indica a primeira posição a partir da qual todos os elementos restantes devem ser zeros.
• Ação: Percorremos o array de idxParaPreencher até o final, atribuindo 0 a cada posição.

Resultado Final: [1, 3, 12, 0, 0]

Implementação em TypeScript (Abordagem de Cópia e Preenchimento)

Esta abordagem realiza a cópia dos elementos não-zero e, em uma segunda etapa, preenche as posições restantes com zeros.

function moverZeros(arrayNumeros: number[]): void {
    let indicePreenchido = 0; // Ponteiro para a próxima posição válida de um não-zero

    // Primeira passada: move todos os não-zeros para o início
    for (let i = 0; i < arrayNumeros.length; i++) {
        if (arrayNumeros[i] !== 0) {
            arrayNumeros[indicePreenchido] = arrayNumeros[i];
            indicePreenchido++;
        }
    }

    // Segunda passada: preenche o restante com zeros
    for (let i = indicePreenchido; i < arrayNumeros.length; i++) {
        arrayNumeros[i] = 0;
    }
}

Implementação em TypeScript (Abordagem de Troca In-Place)

Esta é uma versão mais otimizada que realiza as trocas diretamente, evitando a necessidade de uma segunda passagem para preencher os zeros. Se um não-zero é encontrado em uma posição diferente daquela que deveria ser ocupada, eles são trocados. Zeros são implicitamente empurrados para o final.

function moverZerosInPlace(arrayNumeros: number[]): void {
    let proximaPosicaoNaoZero = 0; // Ponteiro para a posição onde o próximo não-zero deve ir

    for (let ponteiroVarredura = 0; ponteiroVarredura < arrayNumeros.length; ponteiroVarredura++) {
        // Se o elemento atual não for zero
        if (arrayNumeros[ponteiroVarredura] !== 0) {
            // Se os ponteiros estão em posições diferentes, significa que há um zero no meio
            // ou o elemento não-zero já está na sua posição correta (proximaPosicaoNaoZero)
            if (ponteiroVarredura !== proximaPosicaoNaoZero) {
                // Realiza a troca: move o não-zero para a frente
                [arrayNumeros[proximaPosicaoNaoZero], arrayNumeros[ponteiroVarredura]] =
                [arrayNumeros[ponteiroVarredura], arrayNumeros[proximaPosicaoNaoZero]];
            }
            // Avança o ponteiro de posição para o próximo não-zero
            proximaPosicaoNaoZero++;
        }
    }
}

Integração em Ambientes ACM/Online Judges (Node.js)

Para ambientes que utilizam entrada/saída padrão, como muitos desafios de programação, é comum precisar ler a entrada de um arquivo ou stream e imprimir a saída formatada. Abaixo, um exemplo de como integrar as funções acima em um contexto Node.js que lê de stdin.

const { readFileSync } = require('fs');

function processarEntradaESaida() {
    try {
        // Lê toda a entrada do stdin
        let dadosEntrada = readFileSync(0, 'utf-8').trim(); // 0 é o file descriptor para stdin
        
        if (!dadosEntrada) {
            return; // Nenhuma entrada, encerra
        }

        // Remove o prefixo 'nums = ' e parseia o JSON
        dadosEntrada = dadosEntrada.replace(/^nums\s*=\s*/, '');
        const arrayParaManipular = JSON.parse(dadosEntrada);

        // Chama a função para mover os zeros (usando a versão in-place por exemplo)
        moverZerosInPlace(arrayParaManipular);

        // Imprime o array resultante como uma string JSON
        console.log(JSON.stringify(arrayParaManipular));

    } catch (erro) {
        console.error("Ocorreu um erro ao processar a entrada:", erro);
    }
}

// Executa a função principal
processarEntradaESaida();

// Exemplo de como seria o 'input.txt':
// nums = [0,1,0,3,12]

// Para executar no terminal:
// node seu_arquivo_solucao.js < input.txt
// A saída seria: [1,3,12,0,0]