Padrão 2: Transformação in-place
Transformar uma matriz sem usar outra matriz (O(1) de espaço extra) é um tipo de problema que parece exigir uma cópia — mas truques de índice resolvem. Dois clássicos: girar a imagem e zerar linhas/colunas.
Tente primeiro: Rotate Image
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 n × n, gire-a 90° no sentido horário, no lugar (sem usar outra matriz). Retorne a matriz girada.
Exemplo: [[1,2,3],[4,5,6],[7,8,9]] → [[7,4,1],[8,5,2],[9,6,3]].
Tentou? Copiar para uma nova matriz girada funciona, mas gasta O(n²) de memória. A teoria abaixo gira no lugar com dois passos simples.
A teoria 1: girar = transpor + inverter
Girar 90° no sentido horário parece complicado de fazer no lugar — mas se decompõe em duas operações fáceis:
- Transpor: espelhar na diagonal principal (trocar
m[i][j]comm[j][i]). Linhas viram colunas. - Inverter cada linha: espelhar horizontalmente.
1 2 3 transpõe 1 4 7 inverte linhas 7 4 1
4 5 6 ───────────▶ 2 5 8 ──────────────▶ 8 5 2
7 8 9 3 6 9 9 6 3
Faça as contas com uma célula para se convencer: o 1 em (0,0) vai para
(0,0) na transposta e depois para (0,2) ao inverter a linha — exatamente
onde o 1 deve ficar após girar 90°. Os dois passos compõem a rotação.
Detalhe que evita um bug clássico: na transposição, o j começa em i + 1. Se
você percorresse a matriz inteira, trocaria cada par duas vezes e voltaria
ao original. Trocar só a metade acima da diagonal faz cada troca uma vez.
O(n²) de tempo (toca cada célula uma vez), O(1) de espaço.
A teoria 2: usar a própria matriz como bloco de notas
Set Matrix Zeroes: se uma célula é 0, zere toda a sua linha e coluna. O perigo é fazer isso "na hora" — o primeiro 0 zeraria células que, lidas depois, disparariam zeros falsos em cascata.
A solução ingênua marca numa matriz auxiliar (O(m·n) de espaço) quais linhas e colunas zerar. O truque in-place: use a primeira linha e a primeira coluna da própria matriz como os marcadores — elas viram o "bloco de notas". Assim o espaço extra cai para O(1).
1. Numa passada, para cada 0 em (r,c): marque grid[r][0]=0 e grid[0][c]=0
(e lembre à parte se a 1ª linha/coluna originalmente tinha algum 0).
2. Numa segunda passada, zere grid[r][c] se grid[r][0]==0 ou grid[0][c]==0.
3. Por fim, zere a 1ª linha/coluna se elas precisavam.
O(m·n) de tempo (poucas passadas), O(1) de espaço — porque os marcadores moram dentro da própria matriz.
A lição que generaliza
Transformação in-place quase sempre vem de duas ideias: (1) decompor a transformação difícil em passos simples e reversíveis (transpor + inverter), e (2) reaproveitar o próprio espaço dos dados como memória auxiliar (a 1ª linha/coluna como marcadores). Quando o enunciado pedir "O(1) de espaço", pergunte: "que estrutura simples compõe isto?" e "dá para anotar dentro da própria entrada?".
🧠 Quiz de fixação
0/41. Como girar uma matriz 90° no sentido horário, no lugar?
2. Na transposição in-place, por que o laço interno começa em j = i + 1?
3. No Set Matrix Zeroes, qual é o truque para usar O(1) de espaço extra?
4. Por que NÃO dá para zerar a linha e a coluna 'na hora' que se encontra um 0?
Resumo
- Girar a imagem: transpor + inverter cada linha → 90° horário, O(n²)/O(1).
- Set Matrix Zeroes: marque nas próprias 1ª linha/coluna, depois zere → O(m·n)/O(1).
- In-place vem de decompor a transformação e reusar o próprio espaço dos dados.
Próxima aula: tratar o grid como um grafo e inundar regiões — DFS.