0238-product-of-array-except-self¶

Description¶

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:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

2 <= nums.length <= 10⁵
-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.)

Solution(Python)¶

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # nums = [1 2 3 4]
        #  i = 0
        #      2 * 3 * 4 = 24
        #   i = 1
        #     1 * 3 * 4 = 12 
        #   i = 2
        #     8
        #   i =3
        #     6
        # bruteforc appraoch -> for eachindex i multiple elemnst except i n^2
        # if store the results in two  array
        #   from front
        #    from back where multiple until last /previuou element 
        #  then  final solution is front(i) * back(i)
        #   one pass but takes extra space
        #  
        #   optimised way is to take result and do
        #      forward multiply option in res itself 
        #    and then do backward multiplication in the res itself
        #   res = [1 1 1 1]
        #   nums  = [1 2 3 4]
        #   forward pass
        #    res[0] = nums[0] 1
        #       i = 1
        #         res[1] = res[0] 1
        #
        #         res[2] = res[0] * res[1] 2
        #         res[3] =  res[0] * res[1] * res[2] 6
        #        
        #          
        #         runnningmultiple = 1
        #         
        #         res[i] = runnningmultiple * nums[i-1] {1 ...n-1}
        #         runnningmultiple *= nums[i-1] 
        #         
        #    res  1 1 2 6
        #  set runnningmultiple = 1
        #    for n - 2 to 0
        #     res[i] = res[i] * runnningmultiple * nums[i+1] {1 ...n-2}
        #    res[3] = 6
        #   looo:
        #    res[2] = 1 *  4  * 2=  8
        #    res[1] = 1 *  4 * 3 = 12
        #    res[0] = 1 * 12 * 2 = 24
        #  
        n = len(nums)
        if not n:
            return []
        res = [1] * n
        running_prod = 1

        for i in range(1, n):
            res[i] = running_prod * nums[i-1]
            running_prod *= nums[i-1]
        
        running_prod = 1
        for i in range(n-2, -1, -1):
            res[i] = res[i] * running_prod * nums[i+1]
            running_prod *= nums[i+1]
        return res