Write product_except_self(nums: list[int]) -> list[int].
Return a list out of the same length where out[i] is the product of every element of nums except nums[i].
- Don't use division. Zeros make division awkward, and the challenge is to do without it. (The tests can't check this, so it's up to you.)
- Run in O(n) time.
Example: [2, 3, 4, 5] gives [60, 40, 30, 24].
[3, 0, 2, -1] gives [0, -6, 0, 0].
Constraints: 2 <= len(nums) <= 10^5; values can be zero or negative, and the product of any subset of them fits in a signed 32-bit integer.
Multiplying the other n - 1 elements separately for each index is O(n²) and fails the large test.
Show hint
split out[i] into two parts: everything to the left of i and everything to the right. Both can be built up with a running product.