Product of Array Except Self medium

Problem Statement

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] Explanation: The product of all the elements of nums except nums[0] is equal to 24. The product of all the elements except nums[1] is equal to 12 etc.

Example 2:

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

Steps to Solve:

The key idea is to avoid division. We can achieve this by calculating prefix and suffix products separately and then combining them.

1. Initialize: Create two arrays, prefix_products and suffix_products, both of the same size as nums. Initialize prefix_products[0] to 1 and suffix_products[len(nums)-1] to 1.

2. Calculate Prefix Products: Iterate through nums from left to right. For each index i, prefix_products[i] will store the product of all elements from nums[0] to nums[i-1].

3. Calculate Suffix Products: Iterate through nums from right to left. For each index i, suffix_products[i] will store the product of all elements from nums[i+1] to nums[len(nums)-1].

4. Combine: Iterate through nums and for each index i, answer[i] will be the product of prefix_products[i] and suffix_products[i].

Explanation:

This approach works because for each element nums[i], we are essentially multiplying all the elements before it (prefix_products[i]) and all the elements after it (suffix_products[i]). This gives us the product of all elements except nums[i]. The use of prefix and suffix arrays avoids the need for division.

Code (Python):

def productExceptSelf(nums):
    n = len(nums)
    prefix_products = [1] * n
    suffix_products = [1] * n
    answer = [1] * n

    # Calculate prefix products
    for i in range(1, n):
        prefix_products[i] = prefix_products[i-1] * nums[i-1]

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

    # Combine prefix and suffix products
    for i in range(n):
        answer[i] = prefix_products[i] * suffix_products[i]

    return answer

Complexity:

• Time Complexity: O(n) - We iterate through the nums array three times.
• Space Complexity: O(n) - We use three arrays of size n (prefix_products, suffix_products, answer). We could optimize space to O(1) by directly writing the result into the answer array, but this makes the code a bit harder to understand.