Simple Python solution in O(n) with constant space


  • 0
    T
    class Solution(object):
        def productExceptSelf(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            n = len(nums)
            output = [0]*n
            
            # Invalid if length of array <= 1
            if n <= 1:
                return None
            
            # Build up in ascending order, by multiplying array so far with current element at each position
            output[0] = nums[0]
            for i in range(1, n-1):
                output[i] = output[i-1] * nums[i]
            
            # Last element is already slotted for the final answer    
            output[n-1] = output[n-2]
                    
            # Build up the product while reading the nums array from the end
            rightProduct = 1
    
            # Case when length of input array, nums > 2
            if n > 2:
                for i in range(n-2, -1, -1):
                    rightProduct = rightProduct * nums[i+1]
                    if i > 0:
                        output[i] = output[i-1] * rightProduct
                    # special case for first element
                    else:
                        output[i] = rightProduct
            
            # For array that is of size 2, simple operation
            else:
                output[0] = nums[1]
            
            return output
    
    

Log in to reply
 

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