[LeetCode] 238. Product of Array Except Self

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

Product of Array can be calculated with the table like:

    
    0   1   2   3
  +---+---+---+---+
0 |   | * | * | * | 
  +---+---+---+---+
1 | * |   | * | * |
  +---+---+---+---+
2 | * | * |   | * |
  +---+---+---+---+
3 | * | * | * |   |
  +---+---+---+---+

As it shows,  result[i]  = product(num[:i])  * product(nums[i:])

Let dp1[i] = product of numbers before nums[i], not include nums[i],

And dp2[i] = product of numbers after nums[i], not include nums[i]

Then result[i] = dp1[i] * dp2[i]

Time Complexity = O ( N )

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        N = len(nums)
        
        # dp1[i] = product of numbers before nums[i], not include nums[i]
        dp1 = [1] * N
        
        # dp2[i] = product of numbers after nums[i], not include nums[i]
        dp2 = [1] * N
        
        for i in range(1, N):
            dp1[i] = nums[i-1] * dp1[i-1]
            
        for i in reversed(range(N-1)):
            dp2[i] = nums[i+1] * dp2[i+1]
        
        return[ dp1[i] * dp2[i] for i in range(N) ]