24 de Março
Matriz espiral
Como percorrer uma matriz em camadas usando limites claros em vez de depender de condições espalhadas.
Matriz Intermediario 20 min TypeScript
Dada uma matriz matrix, retorne todos os elementos em ordem espiral.
Exemplo:
Input:
matrix = [
[1,2,3],
[4,5,6],
[7,8,9]
]
Output: [1,2,3,6,9,8,7,4,5]
O que perceber antes de codar
- O percurso acontece por camadas.
- Cada camada pode ser descrita por quatro limites.
- Os casos de borda aparecem quando sobra uma linha ou uma coluna só.
Erros comuns
- esquecer de checar se ainda existe linha ou coluna antes de percorrer a parte de baixo ou a esquerda
- atualizar limites na ordem errada e repetir elemento
Passo 1 - Entender o percurso por camadas
A ordem espiral não e aleatoria.
Ela percorre:
- a borda de fora
- depois a proxima borda interna
- e assim por diante
Isso e um percurso por camadas.
Passo 2 - Escrever a versão inicial mais direta
A versão inicial natural e:
- manter direção atual
- manter matriz de visitados
- virar quando bater em limite ou celula já vista
Funciona.
Mas pede mais estado do que o necessário.
Passo 3 - Perguntar qual estado realmente importa
Para a camada atual, basta saber:
topbottomleftright
Esses quatro limites dizem exatamente o retangulo ainda não percorrido.
Passo 4 - Percorrer e encolher
Em cada rodada:
- percorra o topo
- percorra a direita
- se ainda existir linha sobrando, percorra o fundo
- se ainda existir coluna sobrando, percorra a esquerda
Depois encolha os limites.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function spiralOrder(matrix: number[][]): number[] {
// sua solução aqui
return []
}
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(m * n)
Espaço: O(1)
Solução 1 - Simulação com visitados
Boa versão inicial porque deixa o percurso explícito.
export function spiralOrder(matrix: number[][]): number[] {
const rows = matrix.length
const cols = matrix[0].length
const visited = Array.from({ length: rows }, () => new Array(cols).fill(false))
const result: number[] = []
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
let directionIndex = 0
let row = 0
let col = 0
for (let count = 0; count < rows * cols; count += 1) {
result.push(matrix[row][col])
visited[row][col] = true
const nextRow = row + directions[directionIndex][0]
const nextCol = col + directions[directionIndex][1]
const outOfBounds = nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols
if (outOfBounds || visited[nextRow][nextCol]) {
directionIndex = (directionIndex + 1) % 4
}
row += directions[directionIndex][0]
col += directions[directionIndex][1]
}
return result
}Funciona, mas existe um modelo mais limpo para esse tipo de percurso.
Solução 2 - Quatro limites
Agora você percorre a camada atual e encolhe o retangulo restante.
export function spiralOrder(matrix: number[][]): number[] {
const result: number[] = []
let top = 0
let bottom = matrix.length - 1
let left = 0
let right = matrix[0].length - 1
while (top <= bottom && left <= right) {
for (let col = left; col <= right; col += 1) {
result.push(matrix[top][col])
}
top += 1
for (let row = top; row <= bottom; row += 1) {
result.push(matrix[row][right])
}
right -= 1
if (top <= bottom) {
for (let col = right; col >= left; col -= 1) {
result.push(matrix[bottom][col])
}
bottom -= 1
}
if (left <= right) {
for (let row = bottom; row >= top; row -= 1) {
result.push(matrix[row][left])
}
left += 1
}
}
return result
}O insight forte aqui e usar os limites como representação do problema restante.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial usa direção atual mais matriz de visitados, mas isso carrega estado demais. A versão forte representa a camada atual com quatro limites:
top,bottom,lefteright. Eu percorro as quatro bordas que ainda existem e depois encolho esses limites, mantendo só estado extraO(1).
Isso mostra que você:
- simplificou o estado
- pensou em camadas, não em movimento solto
- cuidou dos casos de borda de linha e coluna restante
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- percorrer matriz por camadas
- manter limites claros
- fazer simulação com estado mínimo
O ponto não e decorar esse problema.
O ponto e aprender a modelar o que ainda falta percorrer.