LeetCode 238: Produto de Array Exceto Próprio

Dado um array nums, retorne um array onde cada elemento é o produto de todos os outros elementos, exceto o próprio. Restrições: sem divisão e complexidade O(n).

Solução: Divide-se o cálculo em duas partes:

• Produto prefixo (elementos à esquerda)
• Produto sufixo (elementos à direita)

class Solucao {
public:
    vector<int> produtoExcetoSi(vector<int>& valores) {
        int n = valores.size();
        vector<int> resultado(n, 1);
        int prefixo = 1;
        for (int i = 0; i < n; i++) {
            resultado[i] = prefixo;
            prefixo *= valores[i];
        }
        int sufixo = 1;
        for (int i = n - 1; i >= 0; i--) {
            resultado[i] *= sufixo;
            sufixo *= valores[i];
        }
        return resultado;
    }
};

LeetCode 2906: Construção de Matriz de Produto

Dada uma matriz grid, construa uma matriz onde cada elemento é o produto de todos os outros, exceto si próprio. Restrições: sem divisão e reusltado módulo 12345.

Solução: Expansão bidimensional do conceito de prefixo/sufixo:

• Primeira passagem: calcula sufixos (inferior/direita)
• Segunda passagem: multiplica por prefixos (superior/esquerda)

class Solucao {
public:
    vector<vector<int>> construirMatrizProduto(vector<vector<int>>& matriz) {
        const int MOD = 12345;
        int linhas = matriz.size(), colunas = matriz[0].size();
        vector<vector<int>> res(linhas, vector<int>(colunas));
        long sufixo = 1;
        for (int i = linhas - 1; i >= 0; i--) {
            for (int j = colunas - 1; j >= 0; j--) {
                res[i][j] = sufixo;
                sufixo = (sufixo * matriz[i][j]) % MOD;
            }
        }
        long prefixo = 1;
        for (int i = 0; i < linhas; i++) {
            for (int j = 0; j < colunas; j++) {
                res[i][j] = (res[i][j] * prefixo) % MOD;
                prefixo = (prefixo * matriz[i][j]) % MOD;
            }
        }
        return res;
    }
};

Técnicas Comuns

• Núcleo Lógico: Produto = Prefixo × Sufixo
• Otimização: Uso de variáveis temporárias para O(1) espaço adicional
• Manipulação de Dados: Ordem inversa para sufixos, ordem direta para prefixos
• Tratamento de Restrições: Módulo 12345 aplicado durante multiplicações