Python Algorithm Q11
Q11 Product of Array Except Self
Q
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.
Sample Input
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
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.
My Solution <- Given 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
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
tmp1=[1 for i in range(len(nums))]
tmp2=[1 for j in range(len(nums))]
for i in range(len(nums)):
if i == 0: #for i-1 index
continue
tmp1[i] = tmp1[i-1] * nums[i-1]
for j in range(len(nums)):
if j == 0: #for i-1 index
continue
tmp2[j] = tmp2[j-1] * nums[-1-(j-1)]
tmp3 = list(map(lambda x,y : x*y,tmp1, reversed(tmp2)))
return tmp3
a = Solution()
nums = [1,2,3,4]
print(a.productExceptSelf(nums))
#Output: [24,12,8,6]
Question is really intricated when try to solve without any division. To sovle the problem, let’s make an example.
Let an array = [a, b, c, d] What we want for answer is [bcd, acd, abd, abc]. To get answer, you need to multiply right-result to left-result by one and one.
By “arr1[i] = arr1[i-1] * nums[i-1]”, we can get right-direction result. Vice versa, like “arr2[j] = arr2[j-1] * nums[-1-(j-1)]”
Refer the code block below.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
'''
B
↑ ↘
A AB product up & down then result is next right or left
Each right & left array start with "1"
'''
# Right-direction
[1 2 3 4]
1 1 2 6 #multiply with above ↑ way, start from left
# Left-direction
[1 2 3 4]
24 12 4 1 #multiply with above ↑ way, start from right
As you get the two array(right & left mult result), mult it one by one and then get the final result by using map function.
** How to use map function : map(“function”, “the values that will pass through the function”)
So in this question we used map(lambda func, list1, list2), to shorten the code for one by one multiplication.
Overall Review
Not easy to remind the mult algo. Try to think numbers as letters(like math questions…) is the key to the solution. Keep thinking that algo is really close to solving math problem.