<filename>Medium/238.py
# ------------------------------
# 238. Product of Array Except Self
# 
# Description:
# Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
# Example:
# Input:  [1,2,3,4]
# Output: [24,12,8,6]
# Note: Please solve it without division and in O(n).
# 
# Follow up:
# Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
# 
# Version: 1.0
# 09/14/18 by Jianfa
# ------------------------------

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = [1] * len(nums)
        # first multiply from left to right, res[i] = nums[0] * .. * nums[i-1] for i > 0
        for i in range(1, len(nums)):
            res[i] = res[i-1] * nums[i-1]
        
        # then multiply from right to left, res[i] *= nums[i+1] * .. * nums[size-1] for i < size - 1
        # use a right variable to store nums[i+1] * .. * nums[size-1]
        right = 1
        for j in range(len(nums))[::-1]:
            res[j] *= right
            right *= nums[j]
            
        return res

# Used for testing
if __name__ == "__main__":
    test = Solution()

# ------------------------------
# Summary:
# Idea from https://leetcode.com/problems/product-of-array-except-self/discuss/65622/Simple-Java-solution-in-O(n)-without-extra-space
# Multiply the number twice, once from left and once from right. Introduce a variable as a helper,
# use the helper to store temp production of previous numbers.