Python O(n), no extra space solution


  • 0
    M
    def productExceptSelf(self, nums):
            n = len(nums)
            output = nums[:]
            record = 1
            for i in range(0, n):   #nums[i] saves the product of original nums[0]*nums[1]*...*nums[i-1] 
                if i > 0:
                    record, nums[i] = nums[i], record * nums[i-1]
                else:
                    record, nums[0] = nums[0], record
            record = 1
            for i in range(n-1, -1, -1):    #output[i] saves the product of original nums[n-1]*nums[n-2]*...*nums[i+1]
                if i < n-1:
                    record, output[i] = output[i], record * output[i+1]
                else:
                    record, output[i] = output[i], record
            for i in range(0, n):
                output[i] = nums[i] * output[i]
            return output
    

  • 0
    A
        output = nums[:]
    

    This statement declares an array of same size of nums and copies the elements,
    so aren't you using O(n) extra space ?


  • 1
    M

    @arun42 Hi, here is a line in the question description:
    "Note: The output array does not count as extra space for the purpose of space complexity analysis"


Log in to reply
 

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