Multiplicación de arreglo, excepto índice actual - LeetCode 238

Descripción

Dado un arreglo de números enteros llamado nums, devuelve un arreglo llamado answer que en cada posición (answer[i]) contenga el producto de todos los elementos del arreglo, excepto el número en dicha posición (nums[i]).

Se garantiza que el producto de cualquier prefijo o sufijo de nums puede ser representado con un entero de 32 bits.

Tu solución debe ejecutarse en tiempo O(n) y no debe usar la operación de división.

Ejemplo 1

Entrada: nums = [1,2,3,4]
Salida: [24,12,8,6]

Ejemplo 2:

Entrada: nums = [-1,1,0,-3,3]
Salida: [0,0,9,0,0]

Límites:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• Las entradas con las que se prueba la solución garantizan que answer[i] pueda representarse con un entero de 32 bits.

Solución

Esta es una solución propia que puede no ser óptima, es recomendable consultar las soluciones oficiales de LeetCode.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left_products = [1] * n
        right_products = [1] * n
        answer = [1] * n

        # Calculate left products
        for i in range(1, n):
            left_products[i] = left_products[i-1] * nums[i-1]

        # Calculate right products
        for i in range(n-2, -1, -1):
            right_products[i] = right_products[i+1] * nums[i+1]

        # Combine left and right products
        for i in range(n):
            answer[i] = left_products[i] * right_products[i]

        return answer

Fuente del ejercicio: https://leetcode.com/problems/product-of-array-except-self/