[LeetCode] 238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

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

Example 1:

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

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

2 <= nums.length <= 105
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

My Solution

배열에서 자기 자신을 제외한 원소의 곱을 출력하는 문제이다.

(자신을 제외한 왼쪽 값들의 곱) x (자신을 제외한 오른쪽 값들의 곱) = 자신을 제외한 모든 원소의 곱

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left = []
        right = []
        p = 1
        for i in range(len(nums)):
            left.append(p)
            p = p * nums[i]
        
        p = 1
        for i in range(len(nums)-1, -1, -1):
            right.append(p)
            p = p * nums[i]
            
        result = []
        for l, r in zip(left, right[::-1]):
            result.append(l*r)

        return result

$[1, 2, 3, 4]$가 있을 때, 결과는 $[24, 12, 8, 6]$이 되어야 한다.

1. 왼쪽부터 자신을 제외한 곱을 구한다. -> $[1, 1, 2, 6]$
2. 오른쪽부터 자신을 제외한 곱을 구한다. -> $[24, 12, 4, 1]$
3. 두 리스트를 곱한다.