# 238. Product of Array Except Self

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

## me

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left_product = [1] 
        # this `1` is here bc `1` is the Identity Element of Multiplication
        
        for ele in nums[:-1]: # don't want the last
            left_product.append(left_product[-1] * ele)
        
        # left_product[i] is the product of nums[0 ~ i-1]
        
        ans = left_product # copy by ref
        
        right_product = 1
        
        for i, ele in enumerate(nums[-1:0:-1]): # reverse order, w/o the 0-th
            right_product *= ele
            ans[-2-i] = left_product[-2-i] * right_product
            
        return ans

## one pass, `~i`

We can see that

class Solution:
    def productExceptSelf(self, nums):

        res = [1] * len(nums)
        
        l_prod = 1
        r_prod = 1
        
        for i in range(len(nums)):
        
            res[i] *= l_prod
            l_prod *= nums[i]
            res[~i] *= r_prod
            r_prod *= nums[~i]
        
        return res

##

- if allowed division, const space, linear time

$$
b_i = \prod_j a_j / a_i
$$

- no division
- Let’s say we are at position i. We need to know total production form 0 to i-1, and i+1 to N-1
- need two auxiliary arrays
- linear space; linear time
- follow up: require constant space

for i in 0 to N-1:
    left_acc[i] = ...
for j in N-1 to 0:
    right_acc[j] = ...
for k in N-1 to 0:  # this can be left-to-right or right-to-left
    ans[k] = left_acc[k] * right_acc[k]

Collapse the j for-loop into single var (instead of array), and combine j loop and k loop to modify left_acc in place

for i in 0 to N-1:
    left_acc[i] = ...
grow_in_hand = 1
for j in N-1 to 0:
		left_acc[j] *= grow_in_hand
		grow_in_hand *= nums[j]
ans = left_hand

ans = [1] * len(nums)  # why 1? 乘法單位元素, multiplicative identity, identity element of multiplication  
L_prod = 1
R_prod = 1
for i in range(len(nums)):
    ans[i] *= L_prod
    L_prod *= nums[i]
for i in range(len(nums)):
    j = N - 1 - i 
    ans[j] *= R_prod
    R_prod *= nums[j] # j: last ith ele
return res

Or make them into just one for-loop

ans = [1] * len(nums)
L_prod = 1
R_prod = 1
for i in range(len(nums)):
    ans[i] *= L_prod
    L_prod *= nums[i]
    ans[~i] *= R_prod
    R_prod *= nums[~i] # ~i: last ith ele
return res

- `+`
- 0
- `*` `AND`
- 1
- Identity matrix
- union
- {}
- intersection
- U

python ref: [https://hackmd.io/c_7qtFUkSh25GVMkPm-DGg?both](https://hackmd.io/c_7qtFUkSh25GVMkPm-DGg?both)