Python one & two pass solution. O(n) time & O(1) space.


  • 0
    Y
    class Solution(object):
        def productExceptSelf(self, nums):
            left, right = 1, 1
            ans = [1 for i in xrange(0, len(nums))]
            for i in xrange(1, len(nums)):
                left *= nums[i-1]
                ans[i] = left
            for i in xrange(len(nums)-2, -1, -1):
                right *= nums[i+1]
                ans[i] *= right
            return ans
    

    And it can be changed to one pass(loop) with same time and space complexity.

    class Solution(object):
        def productExceptSelf(self, nums):
            left, right = 1, 1
            num = len(nums)
            ans = [1 for i in xrange(0, num)]
            for i in xrange(num):
                ans[i] *= left;
                ans[num-1-i] *= right;
                left *= nums[i];
                right *= nums[num-1-i];
            return ans
    

Log in to reply
 

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