Product of Array Except Self
Module 4 · Arrays & Dynamic Arrays
Problem
Given nums, return answer where answer[i] is the product of every
element except nums[i]. You must run in O(n) and may not use
division. (The output array doesn't count as auxiliary space in the
follow-up: achieve O(1) extra beyond it.)
Examples
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 ≤ n ≤ 10⁵ · products fit in 32 bits · no division.
Attempt it first
First understand why no division: with division you'd multiply everything and divide by nums[i] — but a single zero destroys it (0/0 on the zero's own position), and two zeroes make every answer 0 in a way the trick can't see. The ban isn't arbitrary; the division "solution" is genuinely broken. Now find the real one.