O que é a técnica Two Pointers e sua intuição

Two Pointers é uma técnica que utiliza dois índices (ou ponteiros) para percorrer e manipular estruturas de dados (geralmente arrays ou listas) simultaneamente, geralmente movendo-os em direções diferentes ou na mesma direção, para resolver problemas relacionados a busca, comparação, remoção, ou combinação de elementos.

Intuição:

• Em vez de usar um loop aninhado (O(n²)), você usa dois ponteiros que interagem para reduzir a complexidade.
• Eles aproveitam propriedades como ordenação ou padrão no problema para avançar os ponteiros de forma inteligente.
• Permite resolver problemas que envolvem comparações entre pares, janelas deslizantes ou reorganização de elementos em tempo linear.

Vantagens da técnica Two Pointers

Quando e como identificar que a técnica se aplica

Quando usar Two Pointers:

• Problemas envolvendo arrays ordenados ou que podem ser ordenados.
• Buscar pares ou subarrays que satisfaçam uma condição (ex: soma, diferença).
• Movimentação simultânea para detectar duplicatas, anagramas, ou partições.
• Resolver problemas de janelas deslizantes.
• Manipular dados in-place para remover ou reorganizar elementos.

Como identificar:

• Tem dois índices que precisam caminhar juntos ou em direções opostas.
• Pode evitar loops aninhados com um controle inteligente dos ponteiros.
• O problema exige comparar pares de elementos ou varrer sublistas de forma dinâmica.

Explicação visual e textual passo a passo

Suponha um array ordenado:

[1, 3, 4, 5, 7, 9, 12]
  ^                    ^
 left                right

Objetivo: Encontrar se existe um par cuja soma seja 10.

Passos:

1. Inicialize left no início (0) e right no fim (array.length - 1).
2. Calcule soma = array[left] + array[right].
3. Se soma == 10 → sucesso, retorne os índices.
4. Se soma > 10 → diminuir soma movendo right para a esquerda (right--).
5. Se soma < 10 → aumentar soma movendo left para a direita (left++).
6. Repita até left >= right.

Assim, você percorre o array uma única vez, com complexidade O(n).

5 Exemplos em Java com explicações detalhadas

1. Encontrar se existe um par com soma igual a alvo (array ordenado)

public boolean twoSumSorted(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return true; // par encontrado
        } else if (sum < target) {
            left++; // aumentar soma
        } else {
            right--; // diminuir soma
        }
    }
    return false; // não encontrado
}

Passo a passo:

• left começa no início, right no fim.
• Soma os elementos.
• Dependendo da soma, move o ponteiro adequado para tentar alcançar o alvo.
• Para um array ordenado, esta técnica é eficiente e evita checar todos pares (O(n²)).

2. Remover duplicatas de um array ordenado in-place

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int slow = 0; // slow pointer para posição da próxima escrita
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1; // novo tamanho do array sem duplicatas
}

Passo a passo:

• slow aponta para o índice onde o próximo número único será colocado.
• fast percorre todos os elementos.
• Quando encontra um valor diferente, avança slow e atualiza o valor.
• Complexidade O(n), memória O(1).

3. Verificar se duas strings são anagramas usando Two Pointers (após ordenar)

import java.util.Arrays;

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    char[] arrS = s.toCharArray();
    char[] arrT = t.toCharArray();
    Arrays.sort(arrS);
    Arrays.sort(arrT);

    int left = 0, right = arrS.length - 1;
    while (left < arrS.length) {
        if (arrS[left] != arrT[left]) return false;
        left++;
    }
    return true;
}

Explicação:

• Ordena ambas as strings.
• Percorre ambas simultaneamente com um ponteiro (poderia usar dois, mas um é suficiente aqui).
• Se algum caractere difere, não é anagrama.

4. Encontrar o maior subarray com soma <= k (janela deslizante)

public int maxSubArrayLen(int[] nums, int k) {
    int left = 0, sum = 0, maxLen = 0;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum > k) {
            sum -= nums[left];
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

Passo a passo:

• right expande a janela.
• Soma os elementos dentro da janela.
• Se soma ultrapassa k, move left para reduzir.
• Mantém controle do tamanho máximo da janela válida.
• Complexidade O(n).

5. Intercalar dois arrays ordenados in-place (suposição: espaço extra disponível no final do primeiro array)

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

Passo a passo:

• Ponteiros i e j percorrem os arrays de trás para frente.
• Ponteiro k indica a posição de inserção no resultado.
• Insere o maior elemento entre nums1[i] e nums2[j].
• Assim, evita sobrescrever dados úteis.
• Complexidade O(m+n), espaço O(1).

Comparações com outras abordagens

Dicas específicas para entrevistas técnicas

• Identifique se o array ou string está ordenado: é um sinal clássico para usar dois ponteiros.
• Se precisar encontrar pares ou subarrays, pense em ponteiros para delimitar intervalos.
• Explique sua abordagem claramente para o entrevistador.
• Caso não tenha array ordenado, veja se é possível ordenar (custo pode ser justificado).
• Escreva código limpo, use nomes claros para ponteiros (left, right, slow, fast).
• Lembre de cobrir casos de borda (arrays vazios, elementos iguais, etc).
• Pratique bastante problemas clássicos que usam esta técnica.
• Quando a questão envolver manipulação in-place, pense se é possível resolver com Two Pointers.
• Evite loops aninhados sem necessidade, tente sempre pensar se Two Pointers pode reduzir complexidade.

Exercícios recomendados do LeetCode (com links e dificuldade)

1. Easy: 26. Remove Duplicates from Sorted Array
2. Easy: 167. Two Sum II - Input Array Is Sorted
3. Medium: 344. Reverse String (uso clássico de dois ponteiros para inversão in-place)
4. Medium: 209. Minimum Size Subarray Sum (janela deslizante)
5. Medium: 15. 3Sum (usar two pointers após ordenar para achar trios que somam zero)

Checklist para uso da técnica Two Pointers

• [ ] A estrutura de dados é um array ou string?
• [ ] Os dados estão ordenados ou podem ser ordenados?
• [ ] O problema envolve encontrar pares, trios, subarrays ou reorganização?
• [ ] Posso evitar loops aninhados usando dois índices móveis?
• [ ] Posso avançar os ponteiros de forma condicional para reduzir complexidade?
• [ ] O problema exige solução in-place para economizar espaço?
• [ ] Considerei os casos extremos e fronteiras (array vazio, único elemento)?
• [ ] Minha movimentação dos ponteiros está correta (não estou pulando elementos)?
• [ ] Está clara a lógica para o entrevistador (fale durante a implementação)?
• [ ] Testei mentalmente com exemplos simples?