238. Product of Array Except Self#

Difficulty: Medium

Link to Problem: To see the Product of Array Except Self problem on LeetCode, click here!

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.

Constraints:

  • 2 <= nums.length <= \(10^5\)

  • -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:#

Here’s a Python function to solve this problem:

def productExceptSelf(nums):
    n = len(nums)
    
    # Initialize two arrays to store products to the left and right of each element
    left_products = [1] * n
    right_products = [1] * n
    
    # Calculate products to the left of each element
    left_product = 1
    for i in range(n):
        left_products[i] = left_product
        left_product *= nums[i]
    
    # Calculate products to the right of each element
    right_product = 1
    for i in range(n - 1, -1, -1):
        right_products[i] = right_product
        right_product *= nums[i]
    
    # Calculate the final answer using left and right products
    answer = [left_products[i] * right_products[i] for i in range(n)]
    
    return answer

Explanation:#

  1. n is initialized as the length of the nums array.

  2. Two arrays, left_products and right_products, are created, each with a length of n and filled with ones initially.

  3. left_product is initialized to 1.

  4. A loop iterates through the nums array, from left to right. For each element at index i, it stores the product of all elements to its left (including itself) in the left_products array and updates left_product accordingly.

  5. right_product is initialized to 1.

  6. Another loop iterates through the nums array in reverse order, from right to left. For each element at index i, it stores the product of all elements to its right (including itself) in the right_products array and updates right_product.

  7. The final answer list is constructed by multiplying corresponding elements from the left_products and right_products arrays for each index i.

  8. The function returns the answer list, which contains the desired results.

Overall, this algorithm efficiently computes the product of all elements except the current element, as required. It runs in O(n) time complexity and uses O(n) extra space, which is within the problem’s constraints.

Test cases#

# Example 1: 
nums = [1,2,3,4]
result1 = productExceptSelf(nums)
print(result1)

[24, 12, 8, 6]

# Example 2:
nums = [-1,1,0,-3,3]
result2 = productExceptSelf(nums)
print(result2)

[0, 0, 9, 0, 0]

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the provided code:

Time Complexity:

  1. The first loop iterates through the nums array to calculate the products to the left of each element. This loop runs in O(n) time, where n is the length of the nums array.

  2. The second loop also iterates through the nums array in reverse order to calculate the products to the right of each element. This loop also runs in O(n) time.

  3. The final loop constructs the answer list by multiplying elements from the left_products and right_products arrays. This loop runs in O(n) time.

Since all the loops are independent and sequential, the overall time complexity is O(n).

Space Complexity:

  1. Two additional arrays, left_products and right_products, are created with a length of n, where n is the length of the nums array. Therefore, these arrays consume O(n) extra space.

  2. The left_product and right_product variables are used to keep track of the product to the left and right of each element, respectively. These variables occupy O(1) extra space.

  3. The answer list, which contains the final results, also consumes O(n) space, but it’s not counted toward the extra space complexity analysis as per the problem’s constraints.

Overall, the space complexity is O(n) for this solution.

Challenging Exercises:#

  1. Handle Zeros in the Input: Modify the solution to handle cases where the input array contains zeros. For example, if nums = [0, 1, 2, 3, 0], the output should be [0, 0, 0, 0, 0] because any element multiplied by zero results in zero.

  2. In-Place Modification: Attempt to solve the problem with in-place modification of the nums array, where the output is stored directly in the input array without using any additional space.