25 May 2020 # Product of Array Except Self - LeetCode #238

Being one of the most asked questions and also one of the important problem patterns on LeetCode, the product of array except self problem has become a subject of interest for this blog. It uses a modification of a general approach called prefix sum as an optimal solution.

Letâ€™s dive into it!

You can find the problem statement here: Product of Array except Self - LeetCode

The brute-force approach to solution is simple. For each index in the the array, we calculate the product of every remaining element.

The python code for it will look like this:

```
def productExceptSelf(nums):
n = len(nums)
result = [0]*n
for i in range(n):
product = 1
for j in range(n):
if i != j:
product = product * nums[j]
result[i] = product
return result
```

` Time Complexity: O(N`

^{2})

Space Complexity: O(1) [Not considering the result array]

As we can observe in the brute-force solution, there is a lot of recomputation happening which can be avoided to speed up our code. All we have to do is to precompute all the products from the left side and right side leaving apart the element at their index and have 2 new arrays holding the products. We can do this in two single passes through the array and then we can finally make the result array going through the arrays once more. A more detailed explanation can be seen in the image below:

The time complexity will be reduced to O(N) due to single passes but the space complexity will rise to be O(N) as well.

The python code for this approach is given below:

```
def productExceptSelf(nums):
n = len(nums)
left_prod = [1] * n
right_prod = [1] * n
result = [1] * n
for i in range(1, n):
left_prod[i] = left_prod[i-1] * nums[i-1]
for i in range(n-2, -1, -1):
right_prod[i] = right_prod[i+1] * nums[i+1]
for i in range(n):
result[i] = left_prod[i] * right_prod[i]
return result
```

` Time Complexity: O(N) `

Space Complexity: O(N) [Extra space used for Left Product and Right Product arrays]

We can modify the approach discussed above to not use any extra space by simple trickery.

The python code for it is given below:

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

` Time Complexity: O(N) `

Space Complexity: O(1) [Extra space not used - Disregarding result array]

*Best of Luck! Later.*