class Solution: # @param {integer[]} nums # @return {integer[]} def productExceptSelf(self, nums): p = 1 n = len(nums) output = [] for i in range(0,n): output.append(p) p = p * nums[i] p = 1 for i in range(n-1,-1,-1): output[i] = output[i] * p p = p * nums[i] return output
another approach if no overflow concerns.
def productExceptSelf(self, nums): cntZero = nums.count(0) if not cntZero: prod = reduce(operator.mul,nums) return [prod/x for x in nums] res = [0]*len(nums) if cntZero == 1: res[nums.index(0)] = reduce(operator.mul,(x for x in nums if x)) return res
Sorry I am not very good with complexity. For your solution there are two for loop that loop through the len of nums. why is time complexity O(n) and not O(2n) ?
@qeatzy replace
reduce(operator.mul,(x for x in nums if x)) to
reduce(lambda x, y: x*y if y else x, nums) can be much faster.
@hqpdash is this solution O(n) space instead of O(1) since we are using another output array to store numbers
this is unbelievably brilliant! how did you come up with this amazing idea genius? I think it is not only a programming problem but even a math problem isn't it?
@YaoshuaiZhang They are actually intelligence tests.
In the case someone might be interested. This is the same approach but combining two pointers in one for loop.
class Solution(object): def productExceptSelf(self, nums): """ :type nums: List[int] :rtype: List[int] """ if not nums: return False arr = [1] * len(nums) pi = pj = 1 for i in range(len(nums)): j = -1-i arr[i]*=pi; arr[j]*=pj pi *= nums[i]; pj *= nums[j] return arr
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.