Day 9: Product of Array Except Self - leetcode - Python3

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 <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums 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:

class Solution:

    def productExceptSelf(self, nums: List[int]) -> List[int]:

        result: List[int]=[1] * len(nums)

        #without division

       

        pre=1

        for i in range(len(nums)):

            result[i]=pre #[1,1,2,6]

            pre= pre * nums[i]

       

        post=1

        for i in range(len(nums) -1,-1,-1):

            result[i]= result[i]*post #[24,12,8,6]

            post= post * nums[i]

        return result

Time Complexity: O(n)

Space Complexity: O(1) :

The space complexity of the function is O(1) because the result list is not counted towards the space complexity. Although the result list is created with a length equal to the length of the nums list, it is reused to store the intermediate results and the final output. No additional space is used that scales with the input size, resulting in constant space complexity.

Here's how the code works:

1. Initialize the result list with all elements set to 1. This will serve as the initial values for the product of all elements except self.

2. Calculate the prefix products:

   • Initialize a variable pre to 1.
   • Iterate over the indices of nums using a for loop.
   • Assign the current prefix product pre to the corresponding index in the result list.
   • Multiply pre by the current element in nums to update the prefix product for the next iteration.

   At the end of this loop, the result list will contain the product of all elements to the left of each index.

3. Calculate the postfix products:

   • Initialize a variable post to 1.
   • Iterate over the indices of nums in reverse order using a for loop with a step of -1.
   • Multiply the current element of result by post and assign the result back to the current index in result.
   • Multiply post by the current element in nums to update the postfix product for the next iteration.

   At the end of this loop, the result list will contain the final product of all elements except self.

4. Return the result list.

The algorithm avoids using division to calculate the products by maintaining separate prefix and postfix products. This allows for an efficient solution with a time complexity of O(n) and a space complexity of O(1).