238.Product_of_Array_Except_Self(Medium).md

238. Product of Array Except Self (Medium)

Date and Time: Sep 8, 2024, 11:33 (EST)

Link: https://leetcode.com/problems/product-of-array-except-self/

Question:

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

• 2 <= nums.length <= 10^5

• -30 <= nums[i] <= 30

• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Walk-through:

1. Intuition

Follow the hints, we can build a prefix and postfix to store all the product before (prefix) and after (postfix) nums[i]. prefix[0] is default to be 1, because if we assume nums[0] doesn't exist, the product should be 1, then for prefix[1] = prefix[i-1] * nums[i-1], we want all the product before nums[i], so we just take the previous product which is prefix[i-1] multiply nums[i-1], so we can get the product before nums[i].

Similarly, postfix[-1] should be 1 as well, postfix[-1] is the product except the last element of nums, so we can traverse backward and start from range(len(nums)-2, -1). Then, we calculate postfix[i] = postfix[i+1] * nums[i+1].

Finally, we just multiply each prefix[i] * postfix[i], so we can get the result.

2. Optimized Space Complexity

Instead of creating lists for prefix and postfix, we can just use a output array res. For the first forward iteration in nums, we put the prefix in res by updating res[i] = res[i-1] * nums[i-1]. Later, we use postfix variable to keep track of current product from the backward iteration of nums, and each time we update res[i] *= postfix, and we also update postfix *= res[i].

Python Solution:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        prefix = [1] * len(nums)
        postfix = [1] * len(nums)
        # Store prefix
        for i in range(1, len(nums)):
            prefix[i] = prefix[i-1] * nums[i-1]
        # Store postfix
        for i in range(len(nums)-2, -1, -1):
            postfix[i] = postfix[i+1] * nums[i+1]

        return [prefix[i] * postfix[i] for i in range(len(nums))]

Time Complexity: $O(n)$, n is length of nums.
Space Complexity: $O(n)$

Python Optimimzed Solution:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # left product * right product
        # maintain a list of left product, then multiply by the right product
        # [1, 1, 2, 6], current i = arr[i-1] * nums[i-1]
        # [24, 12, 8, 6], current i = arr[i] * product, product *= nums[i]

        # TC: O(n), SC: O(n)
        res = [1]
        # Left->right, build the res array
        for i in range(1, len(nums)):
            res.append(res[i-1] * nums[i-1])
        # R->L, use a product var
        product = 1
        for i in range(len(nums)-1, -1, -1):
            res[i] *= product
            product *= nums[i]
        
        return res

Time Complexity: $O(n)$
Space Complexity: $O(1)$, since output array doesn't count as extra space.