Product of Array Except Self

mediumFREEArrays & HashingBlind 75

Given an array nums, return an array where each element is the product of all elements except itself. Do not use division.

Output space-separated.

Example

Input

1,2,3,4

Output

24 12 8 6

Reasoning

Input: nums is a list of integers, here 1,2,3,4. Each output position $i$ gets $\prod_{j \ne i} x_j$ , the product of every entry except $x_i$ .
Position 0 drops the $1$ : $2 \cdot 3 \cdot 4 = 24$ .
Position 1 drops the $2$ : $1 \cdot 3 \cdot 4 = 12$ .
Position 2 drops the $3$ : $1 \cdot 2 \cdot 4 = 8$ .
Position 3 drops the $4$ : $1 \cdot 2 \cdot 3 = 6$ .
Output: a list the same length as the input, printed space-separated as 24 12 8 6.
Notice why division is banned: with a zero in the input, as in $-1, 1, 0, -3, 3$ , every position except the zero's own includes that $0$ and becomes $0$ . Only the zero's position survives, at $(-1)(1)(-3)(3) = 9$ , giving 0 0 9 0 0. Dividing a total product by $x_i$ can't recover that $9$ .

Constraints

2 <= len(nums) <= 10^5
-30 <= nums[i] <= 30
The product of any prefix or suffix fits in a 32-bit integer

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The "Product of Array Except Self" problem involves array manipulation and dynamic programming concepts. To tackle this problem, it's essential to understand how to iterate through arrays, perform calculations, and store intermediate results. The problem statement explicitly prohibits the use of division, which means we need to rely on multiplication and accumulation techniques to compute the product of all elements except the current one.

In the context of arrays, it's crucial to grasp the concept of indexing, where each element is assigned a unique index (or position) in the array. We can access and manipulate elements using their indices. Additionally, understanding how to use auxiliary arrays or temporary variables to store intermediate results can be beneficial in solving this type of problem. The problem also touches on the idea of prefix and suffix products, where we calculate the product of all elements before and after a given index, respectively.

The "Product of Array Except Self" problem is an example of a constraint-based problem, where we need to work within specific constraints (i.e., no division) to find a solution. This type of problem requires creative thinking and problem decomposition, where we break down the problem into smaller, manageable sub-problems. By doing so, we can develop an efficient algorithm that meets the problem's requirements.

Algorithm/Approach

The general approach to solving this problem involves using a combination of array iteration and dynamic programming techniques. We can use two passes through the array: one to calculate the prefix products and another to calculate the suffix products. Alternatively, we can use a single pass with some clever indexing and accumulation techniques. The key idea is to avoid using division and instead rely on multiplication and accumulation to compute the product of all elements except the current one.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize an output array with the same length as the input array.
Calculate the prefix products by iterating through the input array from left to right.
Calculate the suffix products by iterating through the input array from right to left.
Combine the prefix and suffix products to obtain the final result.
Alternatively, use a single pass with clever indexing and accumulation techniques.

Common Pitfalls

When implementing the solution, watch out for:

Using division, which is explicitly prohibited.
Incorrectly indexing the input or output arrays.
Failing to handle edge cases, such as an empty input array or an array with a single element.
Using unnecessary variables or data structures, which can increase memory usage.

Time & Space Complexity

The expected time complexity for this problem is O(n), where n is the length of the input array, since we need to iterate through the array at least once. The space complexity is also O(n), as we need to store the output array and potentially some auxiliary arrays or variables. However, it's possible to optimize the space complexity to O(1) by using a single output array and some clever indexing techniques.

solution.py

Python 3.13

Test results