Two Pointers Technique (Técnica dos Dois Ponteiros)
O que é Two Pointers? (Explicação Completa)
Two Pointers é uma técnica onde usamos DOIS ponteiros (índices) que se movem pela estrutura de dados para resolver problemas em O(n) ao invés de O(n²).
TWO POINTERS: DUAS MÃOS EM UMA FILA
Imagine que você tem uma fila ordenada de pessoas por altura:
1.2m1.4m1.5m1.6m1.7m1.8m1.9m2.0m
Ana Beto Carla Diana Eva FabiGui Hugo
↑
esquerda (left)
↑
direita (right)
Você quer encontrar um par que some 3.3m?
Maneira burra:
Comparar cada pessoa com TODAS as outras = O(n²) comparações!
Maneira esperta (Two Pointers):
left = início, right = fim
Se soma > 3.3m, right-- (pessoa mais baixa precisa entrar)
Se soma < 3.3m, left++ (pessoa mais alta precisa entrar)
Só O(n) comparações!
Por Que O(n²) → O(n)? A Magia da Convergência
COMPARAÇÃO: BRUTE FORCE vs TWO POINTERS
ARRAY: [1, 2, 3, 5, 8, 12, 23] TARGET: 15
BRUTE FORCE (O(n²)):
Comparar TODOS os pares:
1+2=3 1+3=4 1+5=6 1+8=9 1+12=13 1+23=24
2+3=5 2+5=7 2+8=10 2+12=14 2+23=25
3+5=8 3+8=11 3+12=15 ← ENCONTROU!
5+8=13 5+12=17 5+23=28
8+12=20 8+23=31
12+23=35
Total: 21 comparações! (n × (n-1) / 2)
Para n = 100: 4.950 comparações!
Para n = 1000: 499.500 comparações!
Para n = 10000: 49.995.000 comparações!
TWO POINTERS (O(n)):
left=0, right=6
↓ ↓
[1, 2, 3, 5, 8, 12, 23]
1 + 23 = 24 > 15 → right--
left=0, right=5
↓ ↓
[1, 2, 3, 5, 8, 12, 23]
1 + 12 = 13 < 15 → left++
left=1, right=5
↓ ↓
[1, 2, 3, 5, 8, 12, 23]
2 + 12 = 14 < 15 → left++
left=2, right=5
↓ ↓
[1, 2, 3, 5, 8, 12, 23]
3 + 12 = 15 = 15 → ENCONTROU!
Total: 4 comparações!
Para n = 100: no máximo 100 comparações
Para n = 1000: no máximo 1000 comparações
Para n = 10000: no máximo 10000 comparações
RESULTADO: 49.995.000 vs 10.000 = 5.000x mais rápido!
Três Padrões Principais de Two Pointers
PADRÃO 1: OPPOSITE ENDS (Pontas Opostas)
Use quando: array ordenado + encontrar par/soma
left = 0 (início)
right = n-1 (fim)
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right] # Encontrou!
elif current_sum < target:
left += 1 # Precisamos de número MAIOR
else:
right -= 1 # Precisamos de número MENOR
return None # Não encontrou
Por que funciona?
• Array ordenado: arr[left] é o MENOR, arr[right] é o MAIOR
• Soma muito pequena? left++ (aumenta a soma)
• Soma muito grande? right-- (diminui a soma)
• Ponteiros "convergem" em direção à resposta!
PADRÃO 2: SAME DIRECTION (Mesma Direção)
Use quando: remover duplicatas, encontrar elementos únicos
slow = 0
fast = 0
# Remover duplicatas de array ordenado:
nums = [1, 1, 1, 2, 2, 3, 4, 4, 5]
slow = 0
for fast in range(len(nums)):
if nums[fast] != nums[slow]: # Novo elemento encontrado!
slow += 1 # Move slow para próxima posição
nums[slow] = nums[fast] # Copia o novo elemento
# Resultado: elementos únicos em nums[0:slow+1]
# [1, 2, 3, 4, 5]
Visualização:
nums: [1, 1, 1, 2, 2, 3, 4, 4, 5]
↑ ↑
slow fast
(1) (1) → igual, só avança fast
nums: [1, 1, 1, 2, 2, 3, 4, 4, 5]
↑ ↑
slow fast
(1) (2) → diferente! slow++ e copia
nums: [1, 2, 1, 2, 2, 3, 4, 4, 5] ← nums[1] = nums[3]
PADRÃO 3: FAST & SLOW (Corrida)
Use quando: detectar ciclos, encontrar ponto médio
slow = head # Move 1 passo por vez
fast = head # Move 2 passos por vez
# Detectar ciclo em linked list:
while fast and fast.next:
slow = slow.next # 1 passo
fast = fast.next.next # 2 passos
if slow == fast:
return True # Ciclo encontrado!
return False # Chegou ao fim, sem ciclo
Por que funciona?
Se há ciclo, fast eventualmente "alcança" slow:
Start
slow:1 passo, fast:2 passos
↓
Node
↓
Node ← slow está aqui
fast: volta e chega aqui
↓
Node
→
CYCLE!
Tempo: O(n), Espaço: O(1) — não usa memória extra!
Por Que É Cache-Friendly?
TWO POINTERS + MEMORY = PERFORMANCE
Arrays são armazenados sequencialmente na memória:
MEMÓRIA
Endereço: 0x1000 0x1004 0x1008 0x100C 0x1010 0x1014 ...
Valor: [1] [2] [3] [5] [8] [12]
↑ ↑
left=0 right=6
Cache line: bytes 0x1000 a 0x103F (64 bytes)
contém [1, 2, 3, 5, 8, 12] E [23, ...]
Acessando arr[left] E arr[right] → ambos na mesma cache line!
Loop típico:
while left < right:
process(arr[left], arr[right]) # Dois acessos por iteração
left += 1 ou right -= 1
• Cada acesso a arr[left] e arr[right] é muito provavelmente cache hit
• Dois ponteiros = no máximo 2 cache misses por iteração
• Para 1000 elementos: ~2000 cache hits, ~4 cache misses
Exemplos do Mundo Real
ONDE TWO POINTERS É USADO NA VIDA REAL
1. VERIFICADOR DE PALÍNDROMO
"A man, a plan, a canal: Panama"
↑ ↑
left right
left = início, right = fim
while left < right:
while not alphanumeric(left): left++
while not alphanumeric(right): right--
if lower(left) != lower(right): return False
left++, right--
return True # É palíndromo!
2. MERGE DE ARRAYS ORDENADOS (como no Merge Sort)
array1 = [1, 3, 5, 7]
array2 = [2, 4, 6, 8]
i = 0 (índice array1)
j = 0 (índice array2)
result = []
while i < len(array1) and j < len(array2):
if array1[i] < array2[j]:
result.append(array1[i]); i++
else:
result.append(array2[j]); j++
# Adiciona os restantes
result.extend(array1[i:]) # O(n) total!
result.extend(array2[j:])
3. CONTAINER WITH MOST WATER (Uber/Meta/Google)
Dado: alturas [1,8,6,2,5,4,8,3,7]
Encontrar: duas linhas que formam o maior container
left=0, right=8
while left < right:
width = right - left
height = min(heights[left], heights[right])
area = width * height
max_area = max(max_area, area)
if heights[left] < heights[right]:
left += 1
else:
right -= 1
Problemas Essenciais
Container With Most Water
Medium
Encontre dois postes que formam o maior container de água.
Resolver no LeetCode →
Trapping Rain Water
Hard
Calcule água presa entre barras (2D version do container).
Resolver no LeetCode →
Remove Duplicates from Sorted Array
Easy
Remova duplicatas in-place e retorne o novo length.
Resolver no LeetCode →
Sort Colors (Dutch National Flag)
Medium
Ordene array com 0s, 1s, 2s em uma passagem.
Resolver no LeetCode →🪟 Sliding Window (Janela Deslizante)
O que é Sliding Window? (Explicação Completa)
Sliding Window é uma técnica onde mantemos uma "janela" (subarray ou substring) que desliza pela estrutura de dados, expandindo e contraindo conforme necessário.
SLIDING WINDOW: UMA JANELA QUE DESLIZA
Imagine uma janela de tamanho K=3 deslizando por um array:
Array: [1, 3, 2, 6, 4, 9]
Posição 1:
132 Janela = [1, 3, 2], soma = 6
Posição 2:
326 Janela = [3, 2, 6], soma = 11
Posição 3:
264 Janela = [2, 6, 4], soma = 12
Posição 4:
649 Janela = [6, 4, 9], soma = 19
A janela "DESLIZOU" da posição 1 até a posição 4!
Por Que é O(n) e não O(n²)? A Magia dos Ponteiros
CADA ELEMENTO ENTRA E SAI EXATAMENTE UMA VEZ!
ANÁLISE DE COMPLEXIDADE:
Abordagem naive (todas as janelas possíveis):
Para cada posição inicial i:
Para cada posição final j (j >= i):
Processar janela de i a j
Isso gera O(n²) janelas!
Para n=1000: 1.000.000 de janelas!
Sliding Window otimizado:
left e right são ponteiros que SÓ AVANÇAM:
right: →→→→→→→→→→→ (n passos)
left: →→→→→→→→→→→→ (n passos)
Total: 2n = O(n)
Cada elemento:
• Entra na janela (right++)
• Sai da janela (left++)
• Máximo 2 operações por elemento!
Janela Fixa vs Variável: Quando Usar Cada Uma
JANELA DE TAMANHO FIXO (Fixed Window)
Use quando: O tamanho da janela é conhecido/fixo
Exemplos: médias móveis, máximos de subarrays de tamanho K
TEMPLATE:
def fixed_window(arr, k):
n = len(arr)
if n < k: return None
# Janela inicial: primeiros k elementos
window_sum = sum(arr[0:k])
max_sum = window_sum
# Deslizar a janela:
for i in range(k, n):
window_sum = window_sum - arr[i-k] + arr[i]
max_sum = max(max_sum, window_sum)
return max_sum
EXEMPLO: Máximo de subarrays de tamanho 3:
arr = [1, 3, 2, 6, 4, 9]
i=0: window = [1, 3, 2], soma = 6, max = 6
i=1: window = [3, 2, 6], soma = 11, max = 11
i=2: window = [2, 6, 4], soma = 12, max = 12
i=3: window = [6, 4, 9], soma = 19, max = 19
JANELA DE TAMANHO VARIÁVEL (Variable Window)
Use quando: O tamanho da janela varia conforme condições
Exemplos: maior substring sem caracteres repetidos
TEMPLATE:
def variable_window(s):
n = len(s)
left = 0
max_len = 0
char_index = {} # último índice de cada caractere
for right in range(n):
char = s[right]
# Se caractere já existe na janela, encolhe
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1
# Atualizar último índice
char_index[char] = right
# Atualizar resposta
max_len = max(max_len, right - left + 1)
return max_len
EXEMPLO: "abcabcbb" → maior substring sem repetição:
right=0: "a" → max=1, left=0
right=1: "ab" → max=2, left=0
right=2: "abc" → max=3, left=0
right=3: "abca" → 'a' existe em left=0, left=1 → "bca"
...
Resultado: 3 ("abc" ou "bca" ou "cab")
Cache Benefits: Por Que Janelas Contíguas São Rápidas
JANELA CONTÍGUA = CACHE-FRIENDLY
A janela é sempre um subarray CONTÍGUO na memória:
Memória:
1 3 2 6 4 9 8 5 7 2
↑ ↑ ↑ ↑ ↑
janela janela janela janela janela
1 2 3 4 5
Para janela de tamanho 3, cada "slide" envolve:
• Remover 1 elemento antigo (left)
• Adicionar 1 elemento novo (right)
Todos os acessos são SEQUENCIAIS na memória!
A CPU faz prefetching automatically!
Cache hit rate altíssimo!
Exemplos do Mundo Real
ONDE SLIDING WINDOW É USADO NA VIDA REAL
1. MÉDIAS MÓVEIS (Finanças/Ações)
Preços: [100, 102, 101, 105, 103, 106]
Média móvel de 3 dias:
• Dia 1-3: (100+102+101)/3 = 101
• Dia 2-4: (102+101+105)/3 = 102.7
• Dia 3-5: (101+105+103)/3 = 103
• Dia 4-6: (105+103+106)/3 = 104.7
2. RATE LIMITING (APIs/Limite de Requisições)
Limitar: 100 requisições por minuto
Janela deslizante:
• Registramos timestamp de cada requisição
• Se > 100 requisições na janela de 1 min → BLOQUEAR
• Janela "desliza" conforme o tempo passa
3. DETECÇÃO DE PATTERN EM STREAMING DATA
Encontrar subarray que soma K em stream de dados
(como detectar fraude em transações ao vivo)
Problemas Essenciais
Longest Substring Without Repeating
Medium
Encontre o comprimento do maior substring sem caracteres repetidos.
Resolver no LeetCode →
Minimum Size Subarray Sum
Medium
Encontre o menor comprimento de subarray cuja soma >= target.
Resolver no LeetCode →
Longest Repeating Character Replacement
Medium
Máximo K substituições para ter caracteres iguais consecutivos.
Resolver no LeetCode →
Permutation in String
Medium
Verifique se existe permutation de s1 como substring de s2.
Resolver no LeetCode →
Fruit Into Baskets
Medium
Encontre a maior subarray com no máximo 2 tipos de frutas.
Resolver no LeetCode →DFS (Depth-First Search)
Quando usar DFS:
Exploração completa, path finding, cycle detection, backtracking, combinations/permutations, topological sort.
def dfs(node, visited):
if not node or node in visited:
return
visited.add(node)
process(node)
for neighbor in node.neighbors:
dfs(neighbor, visited)
if not node or node in visited:
return
visited.add(node)
process(node)
for neighbor in node.neighbors:
dfs(neighbor, visited)
Recursive vs Iterative
Recursivo: Usa o call stack da linguagem. Mais simples de escrever.
def dfs_recursive(node):
if not node:
return
visit(node)
for child in node.children:
dfs_recursive(child) # Call stack cresce...
# Call stack para árvore de profundidade 4:
dfs(A) → dfs(B) → dfs(C) → dfs(D) → return
↑ ↑
Stack Frame Stack Frame
de C fica de B fica
pausado pausado
Iterativo: Usa sua própria stack explícita. Melhor para árvores profundas.
def dfs_iterative(root):
stack = [root]
while stack:
node = stack.pop()
if not visited(node):
visit(node)
# Adiciona filhos em ordem reversa para manter ordem
stack.extend(reversed(node.children))
Stack Overflow e Profundidade
Cada chamada recursiva usa ~1KB de stack. Em árvores com milhões de nós, você pode estourar o stack:
Profundidade 10: 10 KB de stack Seguro Profundidade 1,000: 1 MB de stack Cuidado! Profundidade 10,000: 10 MB de stack Provável stack overflow! Linguagem | Stack default | Max recursion ----------------|---------------|--------------- Python | ~8 MB | ~1000 (sys.setrecursionlimit) JavaScript | ~1 MB | ~10000 Java | ~1 MB/thread | Controlável C++ | ~8 MB | Controlável Solução: Use DFS iterativo para árvores muito profundas!
Casos de Uso Reais:
- Maze solving - encontrar caminho
- File system traversal - DFS em pastas
- Dependency resolution - topological sort
- AI games - minimax, DFS em estados
Problemas Essenciais
Course Schedule
Medium
Detecte se é possível completar todos os cursos (DAG).
Resolver no LeetCode →
Word Search
Medium
Verifique se palavra existe no board (DFS com backtracking).
Resolver no LeetCode →BFS (Breadth-First Search)
Quando usar BFS:
Shortest path (unweighted), level-order traversal, encontrar componentes conectados, shortest transformation sequence.
from collections import deque
def bfs(start):
queue = deque([start])
visited = {start}
while queue:
node = queue.popleft()
process(node)
for neighbor in node.neighbors:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
def bfs(start):
queue = deque([start])
visited = {start}
while queue:
node = queue.popleft()
process(node)
for neighbor in node.neighbors:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
Por que BFS Encontra o Caminho Mais Curto?
BFS explora nível por nível, então quando você encontra o destino, é o caminho com menos arestas:
Grafo: A → B → C
↓ ↘ ↓
D → E → F
BFS a partir de A com destino F:
Nível 0: [A]
Nível 1: [B, D] (distância 1 de A)
Nível 2: [C, E] (distância 2 de A)
Nível 3: [F] (distância 3 de A) ← ENCONTROU!
↑
Primeiro nível que contém F = caminho mais curto!
vs. DFS: poderia encontrar A→D→E→F (4 arestas) primeiro!
Memory: Queue vs Stack
BFS usa mais memória que DFS em grafos com branching factor alto:
Árvore binária com profundidade 10:
• BFS: pode ter até 2^10 = 1024 nós na queue (worst case)
• DFS: usa no máximo 10 stack frames (profundidade)
Grafo estrela (1 centro, 10000 folhas):
• BFS: queue pode ter 10000 vizinhos do centro
• DFS: stack usa apenas 2 nós (centro → folha)
BFS Memory (nós na fronteira) vs DFS (caminho)
BFS: ~10000
DFS: ~2
BFS com Distância e Pai
Para reconstruir o caminho mais curto:
from collections import deque
def bfs_with_path(start, end):
queue = deque([start])
parent = {start: None}
distance = {start: 0}
while queue:
node = queue.popleft()
if node == end:
# Reconstruir caminho
path = []
while node:
path.append(node)
node = parent[node]
return path[::-1] # Inverte
for neighbor in node.neighbors:
if neighbor not in parent:
parent[neighbor] = node
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
return None # Sem caminho
# Exemplo: menor rotação do cofre
# "0000" → "0001" → "0011" → "0111" → "1111"
# 4 passos para abrir! (usando BFS)
Casos de Uso Reais:
- Shortest path GPS - caminho mais curto
- Social networks - amigos de amigos
- Level-order traversal - BST por níveis
- Web crawling - crawling em profundidade
Problemas Essenciais
Binary Tree Level Order Traversal
Medium
Percorra árvore por níveis (zigzag opcional).
Resolver no LeetCode →
Shortest Path in Binary Matrix
Medium
Caminho mais curto do ao em matrix binária.
Resolver no LeetCode →