Intuition

Brute force, but it doesn’t work.

Approach

I had to read the solution. The key is math, the order of a product operation do not affect the final result. Visualization makes it easier.

A*B*C*D = (A*B)*(C*D)

Let’s see one example in action. Consider the following array

n=[2,2,3,2,2]

When calculating the answer for n[2], we are calculating the product of two separated grous (2*2) * (2*2), left L and right R independently.

First we do all the lefts, then all rights. The result would be these two arrays:

L = [1,2,4,12,24]
R = [24,12,4,2,1]

Now because each array is the product of all left elements, and all right elements, the asnwer to the problem is

answer[ith] = L[ith] * R[ith]

[ \begin{aligned} KL(\hat{y} || y) &= \sum_{c=1}^{M}\hat{y}_c \log{\frac{\hat{y}_c}{y_c}} \ JS(\hat{y} || y) &= \frac{1}{2}(KL(y||\frac{y+\hat{y}}{2}) + KL(\hat{y}||\frac{y+\hat{y}}{2})) \end{aligned} ]

Complexity

• Time complexity: O(n)

• Space complexity: O(n)

Code

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        m=len(nums)
        answer = [1] * m
        # Brute force Solution O(n2)
        # for i in range(m):
        #     for j in range(m):
        #         if j==i:
        #             continue
        #         answer[i] *= nums[j]

        L = [1] * m
        R = [1] * m
        product = 1
        for i in range(m):
            if i-1 >= 0:
                L[i] = product
            product *= nums[i]

        product = 1
        for i in reversed(range(m)):
            if i-1 < m:
                R[i] = product
            product *= nums[i]
        for i in range(m):
            answer[i] = L[i] * R[i]

        return answer