[NeetCode 150] Products of Array Discluding Self

Products of Array Discluding Self

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 $O(n)$ time without using the division operation?

Example 1:

Input: nums = [1,2,4,6]

Output: [48,24,12,8]

Example 2:

Input: nums = [-1,0,1,2,3]

Output: [0,-6,0,0,0]

Constraints:

2 <= nums.length <= 1000
-20 <= nums[i] <= 20

Solution

A classic problem. There are 3 kinds of cases.

First, there is no zero in the array. All we need to do is use multiplication law, multiplying all numbers together and the product divided by number at the index is the corresponding answer of that index.

Second, there is only one zero in the array. It is obvious that the answer array will all be zero except where the only zero locates.

Finally, if there are more than one zero in the array, the answer will be a pure-zero array.

Code

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        if nums.count(0) > 1:
            return [0] * len(nums)
        if nums.count(0) == 1:
            answer = [0] * len(nums)
            product = 1
            zero_index = 0
            for i, num in enumerate(nums):
                if num == 0:
                    zero_index = i
                    continue
                product *= num
            answer[zero_index] = product
            return answer
        product = 1
        for num in nums:
            product *= num
        answer = []
        for num in nums:
            answer.append(product//num)
        return answer
            

Remember to use // for the division, otherwise the result will be a float rather than integer.