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 (+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.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.