# Leetcode Problem 238: Product of Array Except Self

Problem description:

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]`

. The product of any prefix or suffix of`nums`

is guaranteed to fit in a 32-bit integer.You must write an algorithm that runs in

`O(n)`

time and without using the division operation.

Since we cannot use the division operator, and the solution has to run in $ O(n) $ time, I figured that I will have to, to some capacity, use prefix/suffix arrays to solve this. But laziness is king, so I tried to brute force my way first hoping for the best,

### 1st attempted Python solution Link to heading

```
# leetcode_238.py
class Solution:
def productExceptSelf(self, nums: list[int]) -> list[int]:
n = len(nums)
res = []
for i in range(0, n):
sentinel = nums[i] # the element to be ignored in the product
product = 1
for j in range(0, n):
current = nums[j]
if j == i:
continue
product *= current
res.insert(i, product)
return res
```

and was greeted with:

```
Time Limit Exceeded
```

So had to go back to thinking about prefix/suffix arrays. Following is the second attempt

### 2nd attempted Python solution Link to heading

```
# leetcode_238.py
class Solution:
def productExceptSelf(self, nums: list[int]) -> list[int]:
n = len(nums)
result = []
for i in range(0, n):
# the final 1 is an initialiser for when the list is empty;
# also chose 1 because it's the neutral element in multiplication
prefix_products = reduce(lambda x, y: x * y, nums[: i], 1)
suffix_products = reduce(lambda x, y: x * y, nums[i + 1:], 1)
total = prefix_products * suffix_products
result.insert(i, total)
return result
```

and was greeted again with:

```
Time Limit Exceeded
```

Yet I couldn’t discard the prefix/suffix intuition has I felt it was the key to solving this. So I figured that I needed to precompute the prefix and suffix arrays, both of which require $ O(n) $ time, but this time are not nested so overall it’s still $ O(n)$, instead of $ O(n^2) $ from previous attempts. After the arrays have been created, we can iterate through the input array while also keeping track of the current index in the input and prefix array, and the next index in the suffix array.

### Python solution Link to heading

```
# leetcode_238.py
class Solution:
def productExceptSelf(self, nums: list[int]) -> list[int]:
n = len(nums)
result = []
prefix_products = [1] * (n + 1)
for k in range(1, n + 1):
prefix_products[k] = prefix_products[k - 1] * nums[k - 1]
reversed_nums = list(reversed(nums))
suffix_products = [1] * (n + 1)
for k in range(1, n + 1):
suffix_products[k] = suffix_products[k - 1] * reversed_nums[k - 1]
suffix_products = list(reversed(suffix_products))
# the solution requires us to iterate one more time through the initial array,
# but this time keeping track of the values of the current index, the previous
# index in the prefix array and the next one in the suffix array.
#
# Note how there's no out of bounds/range error because the prefix and suffix arrays have
# one extra element (the initial default 1)
for i in range(0, n):
prod = prefix_products[i] * suffix_products[i + 1]
result.insert(i, prod)
return result
```

I was happy to have solved this, but it turns out that the code above would fail the follow up question:

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

So the hint here is that there’s a way to compute the prefixes and suffixes without actually storing the values in their own array but in the output array directly, since that is not counted in space complexity.

##### Python statistics Link to heading

```
Runtime: 281 ms - beats 59.26 % of python3 submissions.
Memory Usage: 22.1 MB -- 29.76 % of python3 submissions.
```

##### Complexity analysis Link to heading

Time: $ O(n + n + n) = O(3n) = 3 ~O(n)$, where every $ n $ coincides with the for loops iteration.

Space: $ O(n + m) = O(n + n) = 2 ~ O(n) = O(n) $ since we create two arrays for the prefixes and suffixes.

Share on: