Product of All Other Elements for Each Index Without Division

Given an integer array nums, return an array answer of the same length in which answer[i] is the product of every element of nums except nums[i]. Do not use division, and run in time linear in the length of nums.

Function Signature

def products_except_self(nums: list[int]) -> list[int]:

Rules

• answer[i] multiplies the elements at every index other than i, including any zeros among them.
• Equal values are separate elements: leaving out nums[i] removes only the element at index i, not other elements with the same value.
• Do not use the division operator anywhere in the computation.
• Return the products in index order, one per element of nums.

Constraints

• 2 <= len(nums) <= 10^5
• -30 <= nums[i] <= 30
• the product of every prefix of nums, the product of every suffix of nums, and every value of answer lie between -2^31 and 2^31 - 1

Examples

Example 1

Input: nums = [2, 3, 4, 5]
Output: [60, 40, 30, 24]

For example, answer[1] = 2 × 4 × 5 = 40.

Example 2

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

Only answer[1] leaves out the zero: (-2) × 3 × 1 = -6. Every other product includes it.

Example 3

Input: nums = [0, 4, 0]
Output: [0, 0, 0]

With two zeros, every product still includes at least one of them.