MediumLeetCode #238Arrays & Hashing

Product of Array Except Self

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]. You must write an algorithm that runs in O(n) time and without using the division operation.

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

Examples

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

Output: [24,12,8,6]

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

Output: [0,0,9,0,0]

Solution

Approach

Use prefix and suffix products. For each index, multiply the product of all elements to the left by the product of all elements to the right.

def productExceptSelf(nums):
    n = len(nums)
    result = [1] * n
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

Complexity

Time:O(n)

Space:O(1)

Hints

1.Think about prefix and suffix products
2.Can you compute prefix products in one pass?
3.Then compute suffix products and multiply

Asked at

Google