Product of Array Except Self

The problem description can be found in LeetCode.

Approach

This is a classic problem where we need to pre-calculate something that we are going to use later to build up the solution.

For example, with the following input:

nums = [1, 2, 3, 4]
#       a  b  c  d

We have to obtain:

ans = [24, 12, 8, 6]

Which is:

products = [b * c * d, a * c * d, a * b * d, a * b * c]

So, we need to calculate the result based on the operations listed above. One way to obtain them is to derive such products in two ways:

1. From left to right.
2. From right to left.

In this way, we would get something like:

pre  = [        1,     a, a * b, a * b * c]
post = [b * c * d, c * d,     d,         1]

If we multiply the pre and post elements at the same index, we would obtain the same operations compared to products, which is our solution.

This solution would require $O(n)$ for both time and space.

from typing import List


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

        # left to right
        for i in range(1, len(nums)):
            pre[i] = nums[i - 1] * pre[i - 1]

        # right to left
        for i in range(len(nums) - 2, -1, -1):
            post[i] = nums[i + 1] * post[i + 1]

        return [pre_v * post_v for pre_v, post_v in zip(pre, post)]

However, we can avoid to keep track of the pre and post values, but we can instead build such values directly in the list that stores the solution.

Solution

from typing import List


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

        # left to right
        pre = 1
        for i in range(1, len(nums)):
            pre *= nums[i - 1]
            ans[i] *= pre

        # right to left
        post = 1
        for i in range(len(nums) - 2, -1, -1):
            post *= nums[i + 1]
            ans[i] *= post

        return ans

Complexity

• Time: $O(n)$
• Space: $O(n)$

Where $n$ is the size of the nums list.