Products of Array Except Self

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───

Problem

• Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i].
• Each product is guaranteed to fit in a 32-bit integer.
• Follow-up: Could you solve it in time without using the division operation?

Solution

• Initially, I thought to keep track of products in a list, and then append the upper and lower portions of the array, except the specific nums[i].
  • This works, but is , since it recomputes the product of the left and the product of the right of i.
• Instead, we can compute all prefixes and postfixes in one pass each
  • This way, it’s .

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
	    # time complexity: O(n)
	    # space complexity: O(1)
        products = [1] * len(nums)
 
        prefix = 1
        for i in range(len(nums)):
            products[i] = prefix
            prefix *= nums[i]
 
        postfix = 1
        for i in range(len(nums) - 1, -1, -1):
            products[i] *= postfix
            postfix *= nums[i]
 
        return products

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───