Python solution


  • 0
    class Solution(object):
      # This solution use O(n) time and O(n) space
      def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        N = len(nums)
        if N == 0: return
        
        # Initialzie list of 1, size N
        l_prods, r_prods = [1]*N, [1]*N
    
        for i in range(1, N):
          l_prods[i] = l_prods[i-1] * nums[i-1]
    
        for i in reversed(range(N-1)):
          r_prods[i] = r_prods[i+1] * nums[i+1]
    
        result = [x*y for x,y in zip(l_prods,r_prods)]
        return result
    
      # This solution use O(n) time and O(1) space
      def productExceptSelfSpaceOptimized(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        N = len(nums)
        if N == 0: return
        
        # Initialzie list of 1, size N
        result = [1]*N
    
        for i in range(1, N):
          result[i] = result[i-1] * nums[i-1]
        
        r_prod = 1
        for i in reversed(range(N)):
          result[i] *= r_prod
          r_prod *= nums[i]
    
        return result
    

Log in to reply
 

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