# 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.

**Contents**hide

## 0. Product of Array Except Self: Problem Discussion

### 0.0. IO Format

- Given: A list of integers
`(+ve/-ve)`

:`nums`

- Goal: Return a list of integers
`answer`

such that – - Condition:
`answer[i] = product_of_all(nums) except nums[i]`

- Constraint: O(N) Time,
*division operator not allowed*.

### 0.1. Examples

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

### 1.0. Intuitions

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
`i`

- we again iterate over all the indices
`j`

, where`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

### 2.0. Code

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 = [1]*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

- Time:
`O(N)`

, as per the requirements. O(N + N + N) for computing the right, left and the ans - Space:
`O(N)`

, O(N + N) for the left and right arrays.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022