Product of Array Except Self | LeetCode | Solution Explained
LeetCode 238. Product of Array Except Self. I explain the intuitions and observations and explain the solution in detail. Problem Link.
0. Product of Array Except Self: Problem Discussion
0.0. IO Format
- Given: A list of integers
- Goal: Return a list of integers
answersuch that –
answer[i] = product_of_all(nums) except nums[i]
- Constraint: O(N) Time, division operator not allowed.
It can sound a bit complicated, so let’s take an example.
We see how answer for 0th position is
2 * 3 * 4 * 5 = 120. Similarly, for position 2 is
4 * 2 * 4 * 5. Note how we have not used division operator.
1. Product of Array Except Self: Observations & Logic
So how do we approach this question? Since we can’t use division, one thing we can do is, do exactly as the question says.
- we iterate over all the indices
- we again iterate over all the indices
j != i
- and find their product
There seems to be a lot of repetition in the intermediate states, right? It looks like we can better look at this problem by looking in terms of
elements on the right and
elements on the left. I have colored them differently in the following example.
1.1. Compressing Repetitions
It is clear that from either going right to left, or left to right – we see a lot of repetitions in a particular direction. Is there a way we can make use of this?
This is where the knowledge of cumulative sums will help. In the case of cumulative sums, we would create an array of elements where every next element would be the sum of the current element & the previous elements.
In this question, we will use a cumulative product instead.
Here’s how it looks:
1.2. Formalizing Logic
- We saw that we can use
- cumulative product
- going in both the directions
- now how do we get the answer?
- form the intermediate product states, we can immediately tell that we have to multiply diagonal elements to get the answer. Here’s how that looks
2. Product of Array Except Self: Optimized Implementation
class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: right = list(accumulate(nums, operator.mul)) left = list(accumulate(nums[::-1], operator.mul))[::-1] n = len(nums) ans = *n for i in range(n): if i-1 >= 0: ans[i] *= right[i-1] if i+1 < n: ans[i] *= left[i+1] return ans
2.1. Complexity Analysis
O(N), as per the requirements. O(N + N + N) for computing the right, left and the ans
O(N), O(N + N) for the left and right arrays.
June 13, 2022
January 24, 2022