Padrão 1: Travessia por camadas (espiral)
Percorrer uma matriz em espiral parece exigir uma lógica cheia de exceções. O segredo é não pensar célula a célula, mas em quatro limites que cercam a parte ainda não visitada e encolhem a cada borda percorrida.
Tente primeiro: Spiral Matrix
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Dada uma matriz m × n, retorne todos os seus elementos em ordem espiral (sentido horário, começando no canto superior esquerdo).
Exemplo: [[1,2,3],[4,5,6],[7,8,9]] → [1,2,3,6,9,8,7,4,5].
Tentou? Sem uma estrutura, vira um emaranhado de
ifs e direções. A teoria abaixo organiza tudo com quatro variáveis de limite.
A teoria: quatro limites que encolhem
Imagine quatro paredes cercando a região não visitada: top, bottom,
left, right. A espiral é sempre a mesma sequência de quatro
movimentos, e depois de cada um você empurra a parede correspondente para
dentro:
1. topo: da esquerda p/ direita na linha `top` → top++
2. direita: de cima p/ baixo na coluna `right` → right--
3. base: da direita p/ esquerda na linha `bottom` → bottom--
4. esquerda: de baixo p/ cima na coluna `left` → left++
repita enquanto top <= bottom e left <= right
As duas verificações extras (antes da base e da esquerda) cobrem matrizes não quadradas, onde uma "volta" pode acabar no meio. Veja os limites encolhendo e a célula atual seguindo a espiral — a região clara é o que ainda falta visitar:
Por que é O(m·n) e O(1) de espaço (extra)?
Cada célula é visitada exatamente uma vez ao longo da espiral — são m × n
células, logo O(m·n) de tempo. Fora a lista de saída (que é a resposta,
não conta como extra), usamos só quatro inteiros de limite → O(1) de espaço
extra. Não há como ser mais rápido: você precisa olhar cada célula ao menos
uma vez para listá-la.
A grande ideia: "por camadas"
A espiral é um caso da estratégia camada por camada (ou "casca por casca"): resolva o anel externo, encolha para o anel interno, repita. A mesma ideia reaparece em girar a imagem (próxima aula, onde se gira anel por anel) e em vários problemas de matriz. Quando um problema de grid "envolve as bordas e vai afunilando", pense em limites que encolhem.
Uma variação comum em entrevistas é a inversa: gerar uma matriz em espiral (preencher
1..n²em espiral) em vez de ler. É o mesmo controle de limites — só que escrevendo no lugar de coletar. (Aparece na prova final!)
🧠 Quiz de fixação
0/41. Qual é a ideia central da travessia em espiral?
2. Por que checar 'if top <= bottom' antes de percorrer a base (e 'if left <= right' antes da esquerda)?
3. Qual a complexidade da travessia em espiral de uma matriz m×n?
4. A ideia de 'limites que encolhem' / 'camada por camada' reaparece em qual outro problema da seção?
Resumo
- Espiral = quatro limites (top/bottom/left/right) que encolhem após cada borda.
- Sempre a mesma sequência de 4 movimentos; checagens extras cobrem matrizes não quadradas.
- O(m·n) tempo, O(1) espaço extra.
- "Camada por camada" reaparece em girar a imagem e gerar espiral.
Próxima aula: transformar a matriz no lugar — girar e zerar sem cópia.