LeetCode Problem: 238. Product of Array Except Self

238. Product of Array Except Self

Problem Summary

You’re given an integer array nums of length n. You need to return a new array answer such that:

answer[i] = product of all the elements in nums except the nums[i]

Constraints

• Don’t use division
• Solve it in O(n) time.
• The Product of any prefix or suffix will fit in 32 bit integer.

Understanding the Problem with Example:

Let’s take an example:

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

Here:

• answer[0] = 2 3 4 = 24
• answer[1] = 1 3 4 = 12
• answer[2] = 1 2 4 = 8
• answer[3] = 1 2 3 = 6

We can’t simply calculate the total product and divide it by nums[i] because:

• Division is not allowed.
• Zeroes in the array can lead to incorrect answers or exceptions.

Approaches

1. Using Prefix & Suffix Arrays

• A prefix array: where prefix[i] is the product of all elements before index i.
• A suffix array: where suffix[i] is the product of all elements after index i.

Then: *answer[i] = prefix[i] suffix[i]**

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        prefix = [1] * n
        suffix = [1] * n 
        answer = [1] * n 

        # Building Prefix 
        for i in range(1, n):
            prefix[i] = prefix[ i - 1 ] * nums[i - 1]


        # Building suffix
        for i in range(n - 2, -1, -1):
            suffix[i] = suffix[i+1] * nums[i+1]

        # Buidling Answer
        for i in range(n):
            answer[i] = prefix[i] * suffix[i]

        return  answer

Time & Space Complexity:

• Time: One pass for prefix, one for suffix, one for result. → O(n)
• Space: For prefix, suffix, and answer arrays. → O(n)

Note: It is easy to understand and implement but extra space is used.

2. Optimized Space (using only one output array)

Instead of using separate prefix and suffix arrays:

• use the answer array to store prefix products.
• Then make a second pass from right to left, updating answer[i] with the suffix product.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n 

        # 1. Store prefix product in answer
        prefix = 1
        for i in range(n):
            answer[i] = prefix
            prefix *= nums[i]

        # 2. multiply sufifx product into answer
        suffix = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= suffix
            suffix *= nums[i]
        return answer

Time & Space Complexity:

• Time: Two linear passes → O(n)
• Space: extra space, aside from the answer array → O(1)