Product of Array Except Self | Medium

Date Time 1 min Tags Facebook

Leetcode

Intuition:

  • Create a left list that should be cumulative of [0:i-1] for given i
  • Create a right list that should be cumulative of [i+1:-1] for a given i
  • return list of left[i] * right[~i]

Gotchas:

  • Either the multiplied sum needs to be applied at the proper location AND iteration needs to exclude the last element
  • or there is implied 1 multiplication due to the shift in the iteration

Base cases:

  • Initialize the answer as list of 1
  • Or initialize the left and right accumulation list with implied 1

Solution (Optimized, prealloc):

class Solution(object):
    def productExceptSelf(self, nums):
        N = len(nums)
        output = [1] * N

        sofar = 1
        for i in range(0, N-1):
            sofar *= nums[i]
            output[i+1] = sofar

        sofar = 1
        for j in range(N-1, 0, -1):
            sofar *= nums[j]
            output[j-1] *= sofar

        return output

Solution (Straight forward)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        right = [1]            
        right_sum = 1
        for num in nums[:-len(nums):-1]:
            right_sum *= num
            right.append(right_sum)

        left = [1]
        left_sum = 1
        for i, num in enumerate(nums[:-1]):
            left_sum *= num
            left.append(left_sum)

        return [l*r for l,r in zip(left, right[::-1])]

Complexity Analysis:

O(N)

Comments

comments powered by Disqus