Top K Frequent Elements

O Top K Frequent Elements é um problema clássico que combina contagem de frequência com seleção eficiente dos k maiores elementos.

---

Enunciado (forma comum)

Dado um array de inteiros nums e um inteiro k, retorne os k elementos mais frequentes.

Exemplo

Entrada: nums = [1,1,1,2,2,3], k = 2
Saída: [1,2]

A ordem do resultado geralmente não importa.

---

Ideia central

O problema tem duas etapas distintas:

1. Contar frequências → Hash Map
2. Selecionar os k maiores → Heap, Bucket Sort ou Quickselect

A escolha da técnica define a complexidade final.

---

Abordagem 1 — Heap (mais comum)

Algoritmo

1. Conte as ocorrências usando um Counter

2. Use um min-heap de tamanho k

3. Para cada elemento:

   • Insira no heap
   • Se o tamanho passar de k, remova o menor

4. Retorne os elementos do heap

Implementação (Python)

from collections import Counter
import heapq
 
def topKFrequent(nums, k):
    freq = Counter(nums)
    heap = []
 
    for num, count in freq.items():
        heapq.heappush(heap, (count, num))
        if len(heap) > k:
            heapq.heappop(heap)
 
    return [num for count, num in heap]

Complexidade

• Tempo: O(n log k)
• Espaço: O(n + k)

---

Abordagem 2 — Bucket Sort (ótima)

Explora o fato de que a frequência máxima é n.

Algoritmo

1. Conte frequências
2. Crie n + 1 buckets (índice = frequência)
3. Para cada número, coloque-o no bucket correspondente
4. Percorra os buckets de trás para frente até coletar k elementos

Implementação (Python)

from collections import Counter
 
def topKFrequent(nums, k):
    freq = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
 
    for num, count in freq.items():
        buckets[count].append(num)
 
    result = []
    for f in range(len(buckets) - 1, 0, -1):
        for num in buckets[f]:
            result.append(num)
            if len(result) == k:
                return result

Complexidade

• Tempo: O(n)
• Espaço: O(n)

---

Abordagem 3 — Quickselect (seleção parcial)

Parecida com o QuickSort, mas só garante que os k maiores estejam de um lado.

Ideia

• Converta o mapa em lista
• Use partition por frequência
• Pare quando o pivô estiver na posição correta

Complexidade

• Média: O(n)
• Pior caso: O(n²) (raro na prática)

---

Comparação das abordagens

Técnica	Tempo	Espaço	Quando usar
Heap	O(n log k)	O(n)	k pequeno
Bucket	O(n)	O(n)	Frequência inteira limitada
Quickselect	O(n) médio	O(n)	Performance máxima sem buckets

---

Padrões algorítmicos envolvidos

• Frequency Map
• Heap / Priority Queue
• Bucket Sort
• Selection Algorithms

---

Armadilhas comuns

• Esquecer que frequência ≠ valor
• Usar max-heap quando um min-heap de tamanho k é mais eficiente
• Ignorar que bucket sort só funciona porque a frequência máxima é limitada por n

---

Contexto de entrevistas

Esse problema testa:

• Escolha correta de estrutura de dados
• Análise de trade-offs
• Otimização além da solução trivial