24 de Março
Rotacionar imagem
Como decompor uma rotação de matriz em transformações simples e fazer isso no próprio lugar com segurança.
Matriz Intermediario 20 min TypeScript
Dada uma matriz n x n, rotacione a imagem 90 graus no sentido horario.
No problema original, a rotação deve ser feita no próprio lugar.
Aqui no SeniorPath, implemente a transformação no próprio lugar e depois retorne a própria matriz para comparação.
Exemplo:
Input:
matrix = [
[1,2,3],
[4,5,6],
[7,8,9]
]
Output:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
O que perceber antes de codar
- A matriz e quadrada. Isso simplifica bastante a transformação.
- O desafio não e só "trocar elementos". E mapear coordenadas sem se perder.
- Existe uma decomposicao elegante em duas transformações mais simples.
Erros comuns
- tentar fazer trocas manuais de quatro posições sem um plano claro
- esquecer que o problema original pede fazer tudo no próprio lugar
Passo 1 - Entender a versão inicial mais direta
A forma mais obvia de rotacionar e:
- criar uma matriz nova
- para cada valor, calcular sua nova coordenada
Isso funciona.
Mas gasta memória extra e desvia do pedido original.
Passo 2 - Procurar uma decomposicao mais simples
Em vez de pensar na rotação como um passo magico, quebre assim:
- transpor a matriz
- reverter cada linha
Exemplo:
[1 2 3] [1 4 7] [7 4 1]
[4 5 6] -> [2 5 8] -> [8 5 2]
[7 8 9] [3 6 9] [9 6 3]
Passo 3 - Entender a transposicao
Transpor significa:
- trocar
matrix[row][col]commatrix[col][row]
Para não desfazer trocas, basta percorrer só a parte acima da diagonal principal.
Passo 4 - Reverter cada linha
Depois da transposicao, cada linha só precisa ser invertida com dois ponteiros.
O resultado final e a rotação horaria de 90 graus.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function rotate(matrix: number[][]): number[][] {
// sua solução aqui
return matrix
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n^2)
Espaço: O(1)
Solução 1 - Criar uma nova matriz O(n²)
Boa versão inicial porque o mapeamento de coordenadas fica explícito.
export function rotate(matrix: number[][]): number[][] {
const size = matrix.length
const rotated = Array.from({ length: size }, () => new Array(size).fill(0))
for (let row = 0; row < size; row += 1) {
for (let col = 0; col < size; col += 1) {
rotated[col][size - 1 - row] = matrix[row][col]
}
}
return rotated
}Funciona, mas usa memória extra.
Solução 2 - No próprio lugar com transposicao e reversao usando dois ponteiros
Agora a mesma transformação acontece dentro da própria matriz.
export function rotate(matrix: number[][]): number[][] {
const size = matrix.length
for (let row = 0; row < size; row += 1) {
for (let col = row + 1; col < size; col += 1) {
const temp = matrix[row][col]
matrix[row][col] = matrix[col][row]
matrix[col][row] = temp
}
}
for (const row of matrix) {
let left = 0
let right = row.length - 1
while (left < right) {
const temp = row[left]
row[left] = row[right]
row[right] = temp
left += 1
right -= 1
}
}
return matrix
}O insight forte aqui e decompor uma operação difícil em duas transformações simples e confiaveis.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial cria outra matriz e move cada valor para a coordenada rotacionada. Como o original pede fazer tudo no próprio lugar, a versão forte decompoe a rotação em transpor e reverter cada linha. Isso preserva
O(n²)de tempo e elimina o custo extra deO(1).
Isso mostra que você:
- não ficou preso na troca manual de quatro posições
- soube decompor o problema
- justificou a adaptacao no próprio lugar
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- mapear coordenadas em matriz
- fazer transformação no próprio lugar
- quebrar uma operação complexa em etapas mais simples
O ponto não e decorar esse problema.
O ponto e aprender a decompor transformação de matriz com clareza.