:orphan:

Product of Array Except Self
============================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/product-of-array-except-self/

Given an integer array ``nums``, return *an array* ``answer`` *such
that* ``answer[i]`` *is equal to the product of all the elements of*
``nums`` *except* ``nums[i]``.

The product of any prefix or suffix of ``nums`` is **guaranteed** to fit
in a **32-bit** integer.

You must write an algorithm that runs in ``O(n)`` time and without using
the division operation.

 

**Example 1:**

::

   Input: nums = [1,2,3,4]
   Output: [24,12,8,6]

**Example 2:**

::

   Input: nums = [-1,1,0,-3,3]
   Output: [0,0,9,0,0]

 

**Constraints:**

- ``2 <= nums.length <= 10``\ :sup:```5```
- ``-30 <= nums[i] <= 30``
- The input is generated such that ``answer[i]`` is **guaranteed** to
  fit in a **32-bit** integer.

 

**Follow up:** Can you solve the problem in ``O(1)`` extra space
complexity? (The output array **does not** count as extra space for
space complexity analysis.)

.. highlight:: python

Pattern
-------
Array, Prefix Sum

Solution
--------
Observe that the product of all elements except the element at index i is the
product of all elements ``nums[:i - 1]`` multiplied by the product of all
elements ``nums[i + 1:]``. Iterate through ``nums`` once to compute the product
of all elements ``nums[:i - 1]`` and store the result in a list ``products``.
Start with ``left_product = 1`` and append it to ``products`` before
multiplying with the next element in ``nums``. Iterate through ``nums`` in
reverse to compute the product of all elements ``nums[i + 1:]`` and multiply
the result by the corresponding element in ``products`` to obtains the product
of all elements except the element at index :math:`i`.

Code
----

.. literalinclude:: ../problems/medium/product-of-array-except-self/product_of_array_except_self__approach_1.py
    :language: python
    :lines: 9-

Test
----
>>> from product_of_array_except_self__approach_1 import productExceptSelf
>>> productExceptSelf([1, 2, 3, 4])
[24, 12, 8, 6]
>>> productExceptSelf([-1, 1, 0, -3, 3])
[0, 0, 9, 0, 0]

Complexity
----------
| :math:`n` is the length of the input array
| Time: :math:`O(n)` — pass through array twice
| Auxiliary Space: :math:`O(1)`

.. autofunction:: product_of_array_except_self__approach_1.productExceptSelf