O(n) time and O(1) space Python solution.

  • 0
    class Solution(object):
        def productExceptSelf(self, nums):
            :type nums: List[int]
            :rtype: List[int]
            if not nums:
                return 1
            m = len(nums)
            ans = [nums[0]] * m
            # calculate cumulative product from the left
            for i in range(1, m - 1):
                ans[i] = ans[i-1] * nums[i]
            # fill in cumulative product from the right
            p = 1
            for i in reversed(range(1, m)):
                ans[i] = ans[i-1] * p
                p *= nums[i]
            ans[0] = p
            return ans

Log in to reply

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