LeetCode 238. Product of Array Except Self [Array]

Problem:

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

 

Example:

Input: [1,2,3,4]

Output: [24,12,8,6]

 

Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

 

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

 

-Summary-

1. Create a list that contains the product of all left side elements except the current index of nums element.

2. Create a variable of the right product and multiple with what we have in step 1 (List that contains all the left side products except the current index itself) through the loop. --> this will calculate the product of array except for self.

3. Keep updating the right prod and loop. 

4. Return the answer.

 

-Similar solution-

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        out = []
        p = 1
        
        #Left side production
        for i in range(len(nums)):
            out.append(p)
            p *= nums[i]
        
        p = 1
        
        #right side production
        for i in range(len(nums)-1, -1, -1):
            out[i] *= p
            p *= nums[i]
            
        return out

 

Time Complexity: O(N) --> Need to loop through twice. (2N = N)

Space Complexity: O(1) --> Use variable only except the answer list

 

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]