The problem
Given an integer array nums, return an array answer where answer[i] is the product of every element of nums except nums[i].
Do it in O(n) time and without using division.
Examples
01
- Input
nums = [1, 2, 3, 4]
- Output
[24, 12, 8, 6]
02
- Input
nums = [-1, 1, 0, -3, 3]
- Output
[0, 0, 9, 0, 0]
Constraints
- 2 ≤ nums.length ≤ 10⁵
- −30 ≤ nums[i] ≤ 30
- Every product fits in a 32-bit integer.
The idea
The product of everything except nums[i] is (everything to its left) × (everything to its right). Both sides can be built up as running products.
Pass left to right keeping prefix, the product so far, and write it into answer[i] before multiplying nums[i] in. Then pass right to left keeping suffix the same way, multiplying it into answer[i]. No division, so zeros need no special case.
- Time
- O(n) — two passes
- Space
- O(1) extra — only the output array and two numbers
Solution · every language run against every case
class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) out = [1] * n prefix = 1 # product of everything to the left of i for i in range(n): out[i] = prefix prefix *= nums[i] suffix = 1 # product of everything to the right of i for i in range(n - 1, -1, -1): out[i] *= suffix suffix *= nums[i] return out