238. Product of Array Except Self
## description
## 238. Product of Array Except Self
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
1Input: nums = [1,2,3,4]
2Output: [24,12,8,6]Example 2:
1Input: nums = [-1,1,0,-3,3]
2Output: [0,0,9,0,0]Constraints:
- –2 <= nums.length <= 105
- –-30 <= nums[i] <= 30
- –The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
## notes
### Intuition
The product of all elements except self is equivalent to (product of all elements before i) × (product of all elements after i). We can precompute these prefix and suffix products.
### Implementation
Build a prefix array where prefix[i] is the product of all elements before index i. Initialize prefix[0] = 1 (nothing before it), then prefix[i] = nums[i-1] * prefix[i-1]. Similarly, build a suffix array from right to left where suffix[i] is the product of all elements after index i. The answer at each index is prefix[i] * suffix[i].
### Edge-cases
The edge indices are handled by initializing prefix and suffix with 1s. No division is needed, so zeros in the array don't cause issues.
- –Time: O(n) — three linear passes
- –Space: O(n) — prefix and suffix arrays (can be optimized to O(1) by computing on the fly)
### Complexity
## solution
1from typing import List
2
3class Solution:
4 def productExceptSelf(self, nums: List[int]) -> List[int]:
5 n = len(nums)
6
7 prefix = [1] * n
8 for i in range(1, n):
9 prefix[i] = nums[i - 1] * prefix[i - 1]
10
11 suffix = [1] * n
12 for i in range(n - 2, -1, -1):
13 suffix[i] = nums[i + 1] * suffix[i + 1]
14
15 ans = [1] * n
16 for i in range(n):
17 ans[i] = prefix[i] * suffix[i]
18 return ans
19
20
21
22
23if __name__ == "__main__":
24 # Include one-off tests here or debugging logic that can be run by running this file
25 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
26 solution = Solution()
27