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.

Implementation

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 Analysis

Time Complexity

O(n)

Space Complexity

O(1)

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