238. Product of Array Except Self 🔥

Medium

Problem:

Given an array as input, output an array such that each output[i] is the product of all other elements in the array, excluding itself.

Notice:

1. You must write an algorithm that runs in O(n) time and without using the division operation.

2. You can solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Input: nums = [1,2,3,4] 
Output: [24,12,8,6]

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

Solution:

We need to multiply the result of the product on the left side excluding the current element and the result of the product on the right side excluding the current element.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer = []

        result = 1
        for idx, num in enumerate(nums):
            answer.append(result)
            result *= num

        result = 1
        for i in range(len(nums) - 1, -1, -1):
            answer[i] *= result
            result *= nums[i]
        return answer

Reference: https://www.youtube.com/watch?v=bNvIQI2wAjk