Product of Array Except Self

Try to solve the Product of Array Except Self problem.

We'll cover the following

Statement#

You’re given an integer array, arr. Return a resultant array so that res[i] is equal to the product of all the elements of arr except arr[i].

Write an algorithm that runs in O(n)O(n) time without using the division operation.

Constraints:

  • 2≤2 \leq arr.length ≤103\leq 10^3
  • −30≤-30 \leq arr[i] ≤30\leq 30
  • The product of any prefix or suffix of arr is guaranteed to fit in a 32-bit integer.

Examples#

Created with Fabric.js 3.6.6 Input Output Sample example 1 arr 2 4 0 6 res 0 0 48 0

1 of 2

Created with Fabric.js 3.6.6 Input Output Sample example 2 arr 1 -3 5 7 -11 res 1155 -385 231 165 -105

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Product of Array Except Self

1

What is the output if the following array is given as input?

arr = [-1, 2, 3, 5, 0]

A)

[30, -15, -10, -6, -30]

B)

[0, -15, -10, -6, -30]

C)

[30, -15, -10, -6, 0]

D)

[0, 0, 0, 0, -30]

Question 1 of 30 attempted

Try it yourself#

Implement your solution in the following coding playground:

The optimal solution to this problem runs in O(n) time and takes O(1) space.

Python
usercode > main.py
Input #1
%0 node_01 0 node_11 -1 node_21 2 node_31 -3 node_41 4 node_51 -2
Visualization for Input #1
Product of Array Except Self

You might want to go over the Two Pointers pattern again.

Solution: Container With the Most Water

Solution: Product of Array Except Self