#238 Product of Array Except Self
Given an integer array nums, build an array answer where
answer[i] equals the product of every element of nums except
nums[i].
Two hard rules: your algorithm must run in O(n), and you may not use division. (All the intermediate products are guaranteed to fit in a 32-bit integer, so overflow isn't the puzzle. The structure is.)
Examples
nums = [1, 2, 3, 4][24, 12, 8, 6]answer[0] = 2·3·4 = 24, answer[1] = 1·3·4 = 12, and so on, each slot skips its own element.
nums = [-1, 1, 0, -3, 3][0, 0, 9, 0, 0]The zero at index 2 wipes out every product that includes it; only answer[2], the product of everything else, survives as -1·1·-3·3 = 9.
Constraints
2 ≤ nums.length ≤ 10⁵-30 ≤ nums[i] ≤ 30Every prefix and suffix product fits in a 32-bit integer
The explainer is the good part.
Sign in for the full intuition build-up, every approach from naive to optimal with complexity analysis, progressive hints, and commented solutions in Python, JavaScript, and Java. All free.
Want a taste first? Try a free sample: Two Sum or Valid Parentheses.