238. Product of Array Except Self

MediumLeetCode

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^5
• -30 <= nums[i] <= 30
• The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

How to solve the problem

• Two-Pass Array Traversal

Code

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [1] * n  # Output array, initialized with 1s

        # First pass: accumulate product of all elements to the left of each index
        left = 1
        for i in range(n):
            res[i] = left       # At index i, res[i] is the product of all elements to the left
            left *= nums[i]     # Update left with current element for next iteration

        # Second pass: accumulate product of all elements to the right of each index
        right = 1
        for i in range(n - 1, -1, -1):
            res[i] *= right     # Multiply with the product of all elements to the right
            right *= nums[i]    # Update right with current element for next iteration

        return res

Complexity

• Approach 1: Two-Pass Array Traversal

• Time complexity: O(n)

  • We traverse the array twice, each pass takes O(n) time

• Space complexity: O(1)

  • We only use a constant amount of extra space (excluding the output array)
  • The output array is not counted as extra space as per problem requirements