LC238. Product of Array Except Self

class Solution:
    def productExceptSelf(self, A: List[int]) -> List[int]:
        """ tc O(N)  sc O(N)
        use two seperate array to cache current item in Array A's  left range and right range 's  accumutive product 
        loop through the index get the combined range product res for current index 
        L[i]:  for A[i], its left subarray A[0:i] accumutive product 
        R[i]:  for A[i], its right subarray A[i+1:] accumutive product
        note initilizatio for L[0] and R[n-1] should be 1 
        """
        n = len(A)
        res = []
        L, R = [1]*n, [1]*n
        for i in range(1, n):
            L[i] = A[i-1]*L[i-1]
            
        for i in range(n-2,-1,-1):
            R[i] = A[i+1] * R[i+1]
        for i in range(n):
            res.append(L[i]*R[i])
        return res 

class Solution:
    def productExceptSelf(self, A: List[int]) -> List[int]:
        """ tc O(N)  sc O(1)
        1. since we can't cache range product for each item,  we can take advantage of result array.  Instead of cache left range product into L array,  we first save left range product in result array
        2. loop from right to left and use one varible to cache right range's accumutive product and directly update the final range at index i 
        """
        n = len(A)
        res = [1]*n
        for i in range(1, n):
            res[i] = A[i-1]*res[i-1]
            
        R = 1 
        for i in range(n-1,-1,-1):
            res[i] = res[i] * R
            R = R*A[i]
        return res