24 de Março
Produto do array exceto ele mesmo
Como usar prefixo e sufixo para montar a resposta local de cada índice a partir do contexto dos lados.
Arrays e Prefixo/Sufixo Intermediario 20 min TypeScript
Dado um array de inteiros nums, retorne um array answer tal que answer[i] seja igual ao produto de todos os elementos de nums exceto nums[i].
Você deve fazer isso sem usar divisao.
Exemplo:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
O que perceber antes de codar
- Cada posição depende de tudo menos do valor atual.
- A restrição sem divisao e o centro do problema.
- O produto que você precisa pode ser quebrado em esquerda e direita.
Erros comuns
- tentar usar divisao mesmo com zeros atrapalhando
- montar prefixo correto e esquecer de combinar com o sufixo
Passo 1 — Enxergar o caminho proibido
Sem a restrição, a ideia seria:
- calcular o produto total
- dividir por
nums[i]
O problema proibe isso.
E faz sentido. Zero complica tudo, e o exercicio quer outro raciocínio.
Passo 2 — Perguntar de onde vem a resposta de cada indice
Para answer[i], você precisa do produto de:
- tudo que esta antes de
i - tudo que esta depois de
i
Isso sugere quebrar a informação em duas partes.
Passo 3 — Construir prefixos
Se answer[i] começar guardando o produto da esquerda:
answer[0] = 1answer[1] = nums[0]answer[2] = nums[0] * nums[1]
entao metade da resposta já esta pronta.
Passo 4 — Multiplicar pelos sufixos
Depois faca a passada da direita para a esquerda:
- mantenha um produto acumulado da direita
- multiplique esse valor em
answer[i]
Assim cada posição vira:
prefixoDaEsquerda * sufixoDaDireita
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function productExceptSelf(nums: 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(n)
Espaço: O(1)
Solução 1 — Recalcular para cada indice
Correta, mas lenta demais.
export function productExceptSelf(nums: number[]): number[] {
const answer: number[] = []
for (let index = 0; index < nums.length; index += 1) {
let product = 1
for (let other = 0; other < nums.length; other += 1) {
if (other !== index) {
product *= nums[other]
}
}
answer.push(product)
}
return answer
}Solução 2 — Acumuladores de prefixo + sufixo em O(n)
Agora cada passada acumula metade da informação.
export function productExceptSelf(nums: number[]): number[] {
const answer = new Array(nums.length).fill(1)
let prefix = 1
for (let index = 0; index < nums.length; index += 1) {
answer[index] = prefix
prefix *= nums[index]
}
let suffix = 1
for (let index = nums.length - 1; index >= 0; index -= 1) {
answer[index] *= suffix
suffix *= nums[index]
}
return answer
}Cada indice recebe o produto da esquerda numa passada e o da direita na outra.
O que dizer na entrevista
Uma explicação curta e boa seria:
Sem divisao, cada resposta precisa ser pensada como produto da esquerda vezes produto da direita. Eu faco uma passada guardando prefixos no array de resposta e outra passada multiplicando pelos sufixos acumulados. Isso mantem
O(n)sem precisar recalcular tudo para cada indice.
Isso mostra que você:
- entendeu por que a divisao foi proibida
- quebrou o problema em partes reutilizaveis
- explicou prefixo e sufixo como composição, não como truque
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- combinar informação acumulada dos dois lados
- responder por indice sem recalcular tudo
- trabalhar com
prefix sumou produto de prefixo - transformar dependência global em duas passadas locais
O ponto não e decorar
productExceptSelf.
O ponto e perceber quando a resposta pode ser montada por acumulados parciais.