# Links

Go to my solution

Go to the question on LeetCode

# My Thoughts

**What Went Well**

I knew I had to utilize dynamic programming and maintain a list or variable of the left and right products.

**What Went Wrong**

Implementing left and right products was much more difficult than I thought. I kept thinking of ways that used division, which this problem did not permit.

**What I Learned**

I learned a few different ways to solve this problem, and they each uniquely approached implementing dynamic programming.

**How I Can Improve**

Dynamic programming has proven itself to be a difficult concept to grasp, but all I can keep doing is studying. Analyzing other solutions to recognize patterns in their approaches and watching youtube videos is what I am currently doing.

**Comments**

I am getting better at recognizing when dynamic programming is needed, but knowing exactly how to is still challenging since it is a very generalized term.

**Visual Examples of The Solution**

Example 1, click to view

Example 2, click to view

Example 3, click to view

# Solution Statistics

**Time Complexity**

O(n) - We iterate through the input array nums twice, resulting in O(n*2), but big O ignores constant multiples, resulting in the O(n) time complexity.

**Space Complexity**

O(1) - This problem states that the output array does not contribute to the space complexity, resulting in the O(1) space complexity.

If this were not the case, our space complexity would be O(n) since we create an array with the same number of elements as the input array.

**Runtime Beats**

97.5% of other submissions

**Memory Beats**

88.61% of other sumbissions

# Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
def productExceptSelf(self, nums):
# Create an array that will hold the result
# and has the same number of elements as nums
dp = [1] * len(nums)
# Alter dp so dp[i] = left product
# Left prod = the product of all elements to the left of i
prod = 1
for i in range(len(nums)):
dp[i] = prod
prod *= nums[i]
# Since dp[i] is storing the left product, this loop alters the
# array so each element represents left prod * right prod
# Alter dp so dp[i] = dp[i] * right prod
# Right prod = the product of all elements to the right of i
prod = 1
for i in range(len(nums)-1,-1,-1):
dp[i] *= prod
prod *= nums[i]
return dp