LeetCode75: Python Solution-Product of Array Except Self

Problem

The Product of Array Except Self is a popular coding problem featured in LeetCode 75 that challenges your understanding of array manipulation without using division.

You are given an integer array nums of length n, and you are required to return an array answer such that:

• answer[i] is equal to the product of all elements of nums except nums[i].

Restrictions:

• You must solve it without using division.
• The solution should run in O(n) time.
• Space complexity should ideally be O(1) (excluding the output array).

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 product of any prefix or suffix of the array fits in a 32-bit integer.

Python Solution-Product of Array Except Self

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        # Initialize left and right product arrays
        left_products = [1] * n
        right_products = [1] * n

        # Calculate left products
        left_product = 1
        for i in range(1, n):
            left_product *= nums[i - 1]
            left_products[i] = left_product

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

        # Combine left and right products to get the final result
        result = [left_products[i] * right_products[i] for i in range(n)]

        return result

Step-by-Step Explanation

Step 1: Initialize Arrays

left_products = [1] * n
right_products = [1] * n

• These arrays will hold the prefix (left) and suffix (right) products for each index.
• We start with all values as 1 since multiplying by 1 doesn’t affect the result.

Step 2: Calculate Prefix (Left) Products

left_product = 1
for i in range(1, n):
    left_product *= nums[i - 1]
    left_products[i] = left_product

• For each element, store the product of all elements to its left.

Example (for [1, 2, 3, 4]):

left_products = [1, 1, 2, 6]

Why?
left_products[2] = nums[0] * nums[1] = 1 * 2 = 2

Step 3: Calculate Suffix (Right) Products

right_product = 1
for i in range(n - 2, -1, -1):
    right_product *= nums[i + 1]
    right_products[i] = right_product

• For each element, store the product of all elements to its right.

Example (for [1, 2, 3, 4]):

right_products = [24, 12, 4, 1]

right_products[1] = nums[2] * nums[3] = 3 * 4 = 12

Step 4: Combine Left and Right Products

result = [left_products[i] * right_products[i] for i in range(n)]

• Multiply the prefix and suffix product for each index.

Final Output for [1,2,3,4]:

result = [24, 12, 8, 6]

Time and Space Complexity

• Time Complexity:O(n)
  • We traverse the array 3 times (left, right, and final product).
• Space Complexity:O(n)
  • Due to left_products, right_products, and result.

You can optimize space to O(1) (excluding result) by reusing the result array and computing right products in-place.

This is a classic prefix-suffix product problem that demonstrates how to manipulate arrays without using division and still get the correct result efficiently.

Related Read

Reverse Words in a String