1
# Runtime: 477 ms (Top 13.75%) | Memory: 22.5 MB (Top 18.46%)
2
class Solution:
3
    def productExceptSelf(self, nums: List[int]) -> List[int]:
4
        pre = [1] * (len(nums) + 1)
5
        back = [1] * (len(nums) + 1)
6

7
        for i in range(len(nums)):
8
            pre[i + 1] = pre[i] * nums[i]
9

10
        for i in range(len(nums) - 1, -1, -1):
11
            back[i - 1] = back[i] * nums[i]
12
        for i in range(len(pre) - 1):
13
            nums[i] = pre[i] * back[i]
14

15
        return nums