Given an integer array nums, return an array answer where answer[i] is the product of every element of nums except nums[i]. You must not use division, and the solution should run in O(n) time.
2 * 3 * 4 = 24, for index 1 it is 1 * 3 * 4 = 12, and so on.- 2 <= nums.length <= 10^5
- -30 <= nums[i] <= 30
- Every prefix and suffix product fits in a 32-bit integer
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force multiplies all other elements for each index, which is O(n^2). Division would be O(n) but is banned and breaks on zeros. Notice that the answer for i splits into the product of the prefix before i and the suffix after i. Both can be built with running products, and we can store the prefix products directly in the output array and multiply the suffix in during a second pass, so no extra arrays are needed.
Algorithm
- Create
ansof size n. Setans[0] = 1. - Left to right:
ans[i] = ans[i-1] * nums[i-1](product of everything beforei). - Set
right = 1. Go from right to left:ans[i] *= right, thenright *= nums[i]. - Return
ans.
O(n)Space: O(1) extra (the output array does not count)class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) ans = [1] * n for i in range(1, n): ans[i] = ans[i - 1] * nums[i - 1] # product of everything left of i right = 1 # product of everything right of i for i in range(n - 1, -1, -1): ans[i] *= right right *= nums[i] return ans