Arrays & Hashing · 003Medium
Product of Array Except Self
Given an integer array nums, return an array answer where answer[i] is the product of all elements of nums except nums[i]. You must solve it WITHOUT using division, in O(n) time.
Constraints
- 2 <= nums.length <= 10^5
- -30 <= nums[i] <= 30
- The product of any prefix or suffix fits in a 32-bit integer.
Examples
productExceptSelf([1, 2, 3, 4]) -> [24, 12, 8, 6] productExceptSelf([-1, 1, 0, -3, 3]) -> [0, 0, 9, 0, 0] // one zero productExceptSelf([2, 3]) -> [3, 2] // shortest allowed input productExceptSelf([0, 0]) -> [0, 0] // two zeros wipe everything out productExceptSelf([-2, 3, -4]) -> [-12, 8, -6] // signs matter productExceptSelf([5, 5, 5]) -> [25, 25, 25] // all the same value
Edge cases
- A single zero — every slot except its own becomes 0.
- Two or more zeros — the whole answer is 0.
- FOLLOW-UP
- Can you solve the problem in O(1) extra space complexity? (The output array does not count
- as extra space.)
Show the target complexity (spoiler)
- Naive
- O(n^2) time — recompute the product for each index.
- Target
- O(n) time, O(1) extra space (output excluded) — a prefix pass then a suffix pass, accumulating into the result array.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/01-arrays-hashing/003-product-of-array-except-self.js ./practice c 003