[LeetCode] 238. Product of Array Except Self

1. 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]

2. Thoughts

2.1 First thought (Using Division Operator)

1. multiply all elements -> product
2. return a list with product divided by itself.

However, this was not sufficient, as I did not consider "0".

Therefore, I had to add:
0. make a flag and do when encounter 0:
1. if first time flag (which if stayed till end means only 1 zero)
-> [0] for all but that particular element( which the value will equal to product for the answer)
2. if second time flag (which means multiple zero, which will end with all zeros)
-> return [0] times len of list

This is when I realized that I cannot use a division operator..

2.2 Second Thought

Honestly, I had to get some help for this one:
0. make two lists: left, right
1. traverse through list and make left list the product of every num on the left of nums[i]
2. reversely traverse and fill right
3. return list with left * right

3. Tips learned

Certainly! The prefix-suffix approach is quite intuitive once you understand the terms and how they're applied in this problem.

Prefix & Suffix Definitions:

1. Prefix: In the context of this problem, the prefix for an element at index (i) in nums refers to all the elements before it (from the start of the array to (i-1)).
2. Suffix: The suffix for an element at index (i) refers to all the elements after it (from (i+1) to the end of the array).

Approach:

1. Calculate Prefix Products: You start with a temp variable initialized to 1. As you traverse the nums array, you keep multiplying temp with the current number. At each step, temp represents the product of all numbers before the current one (i.e., the prefix product). You store this product in the ans array.
2. Calculate Suffix Products: After the first loop, the ans array contains the prefix products. Now, you traverse the nums array in reverse, doing the same multiplication with a new temp variable. At each step in this reversed traversal, temp represents the product of all numbers after the current one (i.e., the suffix product). You multiply the current value in the ans array (which is the prefix product) with this temp to get the product of all numbers except the current one.

Example:

For nums = [1,2,3,4],

1. After the prefix loop:

   • For index 0 (value 1): prefix product is 1 (no numbers before it)
   • For index 1 (value 2): prefix product is 1 (product of all numbers before 2)
   • For index 2 (value 3): prefix product is 2 (product of 1 and 2)
   • For index 3 (value 4): prefix product is 6 (product of 1, 2, and 3)

   So, ans becomes [1, 1, 2, 6].

2. After the suffix loop:

   • For index 3 (value 4): suffix product is 1 (no numbers after it)
   • For index 2 (value 3): suffix product is 4 (only number after 3)
   • For index 1 (value 2): suffix product is 12 (product of 3 and 4)
   • For index 0 (value 1): suffix product is 24 (product of 2, 3, and 4)

   Now, we multiply the prefix products (from ans) with these suffix products: [1*24, 1*12, 2*4, 6*1] which gives the final ans as [24, 12, 8, 6].

This approach allows us to solve the problem in (O(n)) time without using division.

4. My solution

4.1 With Division

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        product = 1
        is_zero = -1
        for i, num in enumerate(nums):
            if num == 0:
                if is_zero != -1:
                    return [0] * len(nums)
                is_zero = i
            else:
                product *= num
        if is_zero != -1:
            return [0] * is_zero + [product] + [0] * (len(nums) - is_zero - 1)
        return [(product // num) for num in nums]

Without Division:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans = [1] * len(nums)

        temp = 1
        for i, num in enumerate(nums):
            ans[i] *= temp
            temp *= num

        temp = 1
        for i, num in enumerate(reversed(nums)):
            ans[len(nums) - i - 1] *= temp
            temp *= num

        return ans
    

5. AI Solution and Improvements

Your solution is efficient and runs in (O(n)) time complexity as required by the problem. The approach you've used is commonly known as the "prefix products" and "suffix products" approach, where in the first pass you compute the product of all elements to the left of nums[i] and in the second pass you compute the product of all elements to the right of nums[i].

To make your code more Pythonic and readable:

1. Instead of using enumerate(reversed(nums)), you can use a reversed range for the second loop.

Here's the improved code:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [1] * n

        temp = 1
        for i in range(n):
            ans[i] *= temp
            temp *= nums[i]

        temp = 1
        for i in range(n - 1, -1, -1):
            ans[i] *= temp
            temp *= nums[i]

        return ans

The algorithm you've provided is the most optimal for this problem, so there's no need for a different algorithm. The changes here are merely for clarity and Pythonic style.