Product of Array Except Self
MediumArrays & Hashing · Apple
Given an integer array nums, return an array answer of the same length where answer[i] is the product of every element of nums except nums[i].
Requirements:
- Run in
O(n)time. - Do not use division (so you cannot divide a total product by
nums[i], which would also break on zeros).
Follow-up: can you use only O(1) extra space? The returned answer array does not count as extra space.
Example 1
- Input:
- nums = [2,3,4,5]
- Output:
- [60,40,30,24]
- Explanation
- Each position multiplies the other three: 3 x 4 x 5 = 60, 2 x 4 x 5 = 40, 2 x 3 x 5 = 30, and 2 x 3 x 4 = 24.
Example 2
- Input:
- nums = [3,-1,0,2]
- Output:
- [0,0,-6,0]
- Explanation
- Every position except index 2 includes the 0 in its product, so it is 0. Index 2 multiplies everything else: 3 x -1 x 2 = -6.
Example 3
- Input:
- nums = [0,4,0]
- Output:
- [0,0,0]
- Explanation
- With two zeros, every position still has at least one zero among the other values, so every result is 0.
Constraints
- 2 ≤
nums.length≤ 105 - -30 ≤
nums[i]≤ 30 - The product of any prefix or suffix fits in a 32-bit integer
- Do not use division