🔗 submission url

🧩 Problem: Product of Array Except Self

LeetCode link

Description

Given an integer arraynums, returnan arrayanswersuch thatanswer[i]is equal to the product of all the elements ofnumsexceptnums[i].The product of any prefix or suffix ofnumsisguaranteedto fit in a32-bitinteger.You must write an algorithm that runs inO(n)time and without using the division operation.

Examples

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 <= 105
-30 <= nums[i] <= 30
The input is generated such thatanswer[i] is guaranteed to fit in a32-bitinteger.

Follow up:Can you solve the problem in O(1) extra space complexity? (The output arraydoes notcount as extra space for space complexity analysis.)

---

My Solution

⏱ Runtime: 11 ms
🧠 Memory: 23.1 MB

Code

from copy import deepcopy
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        num_zeros = nums.count(0)
        if num_zeros == 0:
            product = 1
            for num in nums:
                product *= num
            answer = [product // num for num in nums]
        elif num_zeros == 1:
            zero_i = nums.index(0)
            answer = [0] * len(nums)
            nums.remove(0)
            product = 1
            for num in nums:
                product *= num
            answer[zero_i] = product
        else:
            answer = [0] * len(nums)
        
        return answer

Approach

Trying not to repeat same operation, I multiplied all nums and devided in nums[i] for answer[i]
But, failed for the case including 0 in nums.
So, I splited case to
1. No zero
2. One zero : anwer[i] = 0 except for i that nums[i] = 0
3. Greater than eqaul to 2 zeros : answer[i] = 0

Python Grammar

a_list = [1, 2, 4, 0, 5]
# remove FIRST element with VALUE
a_list.remove(0)  # [1, 2, 4, 5]

b_list = [1, 2, 4, 0, 5, 0]
# return FIRST index of VALUE
i = b_list.index(0)  # 3

---

🔁 Feedback

Other Solution

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        prefix_product = 1
        postfix_product = 1
        result = [0]*n
        for i in range(n):
            result[i] = prefix_product
            prefix_product *= nums[i]
        for i in range(n-1,-1,-1):
            result[i] *= postfix_product
            postfix_product *= nums[i]
        return result

Algorithm

Prefix Sum Array.
If you make stacked sum array, you can build Prefix Sum Array w/ O(N).
And you can calculate sum of interval (left to right) w/ O(1).

array = [1, 5, 4, 7, 2, 9, 4, 3]
prefix = [1, 6, 10, 17, 19, 28, 32, 35]

# If I want to get sum of array[2] ~ array[4]
 L=2, R=4
 anwer = prefix[R+1] - prefix[L]

Explanation

Variation of Prefix Sum array which can make it O(N).

nums = [n0, n1, n2, n3]
# After first loop
# for i in range(n):
#     result[i] = prefix_product
#     prefix_product *= nums[i]
result = [1, n0, n0*n1, n0*n1*n2]
# After second loop
# for i in range(n-1,-1,-1):
#     result[i] *= postfix_product
#     postfix_product *= nums[i]
result = [(n1*n2*n3), n0*(n2*n3), n0*n1*(n3), n0*n1*n2]

💬 Review & Thoughts

• Don't afraid of submitting! Too much thinking!