Python O(n) time beat 99.78%


  • 1
    W

    I keep a backward cumulative product in a new list(as commented in code), which will be the output in the end. After iterating through the nums from right to left, we then iterate from the left to right. This time I keep the forward cumulative product along the way, and also modify the backward list to be the output.

    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # backward[i] := nums[i+1] * ... * nums[len(nums) - 1]
        backward = [1 for x in nums]
        back_sofar = 1
        for i in range(-2, -len(nums)-1, -1):
            back_sofar *= nums[i+1]
            backward[i] = back_sofar
        forward_sofar = 1
        for j in range(0, len(nums)):
            backward[j] = forward_sofar * backward[j]
            forward_sofar *= nums[j]
        return backward
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.