> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/arrays]
> [project group:: Neetcode 150]
> [difficulty:: medium]
> [status:: done]
> [link:: https://leetcode.com/problems/product-of-array-except-self/]
> [up:: [[Leetcode MOC]]]
## Problem
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.
**Example 1:**
**Input:** nums = [1,2,3,4]
**Output:** [24,12,8,6]
**Example 2:**
**Input:** nums = [-1,1,0,-3,3]
**Output:** [0,0,9,0,0]
**Constraints:**
- `2 <= nums.length <= 105`
- `-30 <= nums[i] <= 30`
- The product of any prefix or suffix of `nums` is **guaranteed** to fit in a **32-bit** integer.
**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.)
## Solution
### Mine
#### Python
```python
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
prefix = [None] * len(nums)
postfix = [None] * len(nums)
answer = []
for idx, _ in enumerate(nums):
print(f"{idx=}")
if idx == 0:
prefix[idx] = 1
postfix[-1] = 1
else:
prefix[idx] = nums[idx - 1] * prefix[idx - 1]
postfix[-idx - 1] = postfix[-idx] * nums[-idx]
for idx in range(len(nums)):
answer.append(prefix[idx] * postfix[idx])
return answer
```
^o7zoia
#### Rust
### Neetcode's
```python
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
answer = [1] * len(nums)
prefix = 1
for idx, _ in enumerate(nums):
answer[idx] = prefix
prefix *= nums[idx]
postfix = 1
for idx in range(len(nums) - 1, -1, -1):
answer[idx] *= postfix
postfix *= nums[idx]
return answer
```
## Things I Learned
### Neetcode
So far in the video, it seems to be along the lines of my thinking [[238. Product of Array Except Self#^dwafg8|here]]. But what's crucial is that there are prefix and postfix lists that are populated with the product of every number before and after that point. ^qfxz5q
[[238. Product of Array Except Self#^o7zoia|My solution]] is $O(n)$ time and space. We can actually improve it by storing pre and postfix in the answer list, discarding the prefix and postfix lists (output array doesn't count as extra space).
To do this, two passes:
First, iterate through input list, and add prefix calculation to each position in the answer list.
![[Pasted image 20230205134057.png]]
Next, iterate backwards through and multiply postfox by that position.
![[Pasted image 20230205134217.png]]
## Scratchpad
Have 3 variables: the prefixes (list), the current (held back) item, and suffixes. For each item, split the lists, then multiply them all together minus the held back one, then move it to prefix list. ^dwafg8
However the multiplication might still be $O(n)$, so there might be a way to iterate through the list and then do multiple multiplications. I think it would still be $O(n^2)$ though....
Going to do [[238. Product of Array Except Self#^qfxz5q|this]], and see if I can get it on my own before the rest of the video.