218. Product of Array Except Self
From an integer array nums, build a same-length array answer in which slot i holds what you get by multiplying every entry of nums together while skipping the one at index i.
Two house rules make this interesting: your solution must run in O(n) time, and you may not use division (dividing the total product by each element falls apart the moment a zero shows up, anyway).
Every prefix product and every suffix product of nums is guaranteed to fit in a 32-bit signed integer.
Example 1:
Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Explanation: answer[0] = 2·3·4 = 24, answer[1] = 1·3·4 = 12, answer[2] = 1·2·4 = 8, answer[3] = 1·2·3 = 6.
Example 2:
Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
Explanation: Every position whose complement still contains the 0 gets 0; only answer[2] = (-1)·1·(-3)·3 = 9 escapes it.
Constraints:
- 2 ≤ nums.length ≤ 10⁵
- -30 ≤ nums[i] ≤ 30
- Every prefix product and every suffix product of nums fits in a 32-bit signed integer.
- Required: O(n) time, and no division.
Hints:
The product of everything except nums[i] is (product of everything left of i) × (product of everything right of i). Can you precompute those two quantities for every i?
Build prefix products in one left-to-right pass. Then sweep right-to-left carrying a running suffix product and multiply it into the answer as you go — the output array itself can hold the prefixes, so extra space drops to O(1).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 3, 4]
Expected output: [24, 12, 8, 6]