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.

Product of Array Except Self: sample test case
Product of Array Except Self: sample test case

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
Product of Array Except Self: finding the intermediate states
Product of Array Except Self: finding the intermediate states

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.

Product of Array Except Self: finding the intermediate states' divisions
Product of Array Except Self: finding the intermediate states’ divisions

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:

Product of Array Except Self: Finding the cumulative multiplications for both the directions
Product of Array Except Self: Finding the cumulative multiplications for both the directions

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
Product of Array Except Self: Putting it all together
Product of Array Except Self: Putting it all together

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.

    Leave a Reply

    Your email address will not be published. Required fields are marked *