238. Product of Array Except Self

Description:

https://leetcode.com/problems/product-of-array-except-self/description/

 

If we are in nums[0], then output should be the product of all variables in array except nums[0]. I used the division operation, but the problem ask me to avoid using division operation. In addtion, the time complexity should be less than O(N), and space complexity is O(1).

 

Solution1(not answer): 

Brute Force Algorithms

We can use brute force here, but doesn't work for the problem. The reason is that time complexity here is O(N^2), and space complexity is O(1). So, the solution for this problem will be DP algorithms

 

Solution2:

DP algorithms description

We can see that we divide by two list which are name "before and after". In the before list, we put the product of variable before nums[i], and append to right in the list. In the after list, we put the product of variable after nums[i], and append to left in the list. The thing is that the products should be initialized by "1" not "0", because 0 products any numbers is "0".

We have two list before and after. In after, we did for loop reverse. For example, [1, 2, 3, 4] and we fill the value from 3, 2, 1 (not 1, 2, 3). Append the value from right to left. The list name products, we can figure it out zip the before and after, and b & a run each list, and we append the b * a. And return products.

 

Time complexity: O(3N) --> O(N)

Space complexity: O(2N) --> O(N)