TC - O(n)
SC - O(1)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:

        product = [1]*len(nums)

        # do a forward pass and accumulate the answers
        for i in range(1, len(nums)):
            product[i] = product[i-1]*nums[i-1]

        reverse_cum_product = 1
        # do a backward pass and accumulate the answers again
        for i in range(len(nums)-1, -1, -1):
            product[i] = product[i]*reverse_cum_product
            reverse_cum_product *= nums[i]

        return product