LeetCode 238: Product of Array Except Self Solution in Python – A Step-by-Step Guide

What Is LeetCode 238: Product of Array Except Self?

In LeetCode 238: Product of Array Except Self, you’re given an integer array nums, and your task is to return a new array where each element at index i is the product of all elements in nums except nums[i]. The catch? You should aim for O(n) time complexity without using division, though division is technically allowed if handled properly. This contrasts with linked list tasks like LeetCode 237: Delete Node in a Linked List, focusing on array manipulation.

Problem Statement

• Input: An integer array nums.
• Output: An array where each element is the product of all other elements.
• Rules: O(n) time preferred, no division ideally, O(1) extra space (excluding output).

Constraints

• Array length: 2 to 10^5.
• Values: -30 to 30.
• Product fits in a 32-bit integer.

Examples

• Input: nums = [1,2,3,4]
• Output: [24,12,8,6]
• 24 = 2*3*4, 12 = 1*3*4, 8 = 1*2*4, 6 = 1*2*3.
• Input: nums = [-1,1]
• Output: [1,-1]
• 1 = 1, -1 = -1.
• Input: nums = [0,2]
• Output: [2,0]
• 2 = 2, 0 = 0.

Understanding the Problem: Product Except Self

To solve LeetCode 238: Product of Array Except Self in Python, we need to compute the product of all elements except the one at each index. This isn’t about tree traversal like LeetCode 236: Lowest Common Ancestor of a Binary Tree—it’s an array challenge. A naive approach (multiplying all others for each index) takes O(n²), which is too slow. We’ll explore two methods: 1. Best Solution (Two-Pass Prefix-Suffix): O(n) time, O(1) space (excluding output)—division-free and optimal. 2. Alternative Solution (Division-Based with Zero Handling): O(n) time, O(1) space—simpler but uses division.

Let’s dive into the best solution.

Best Solution: Two-Pass Prefix-Suffix Approach

Why This Is the Best Solution

The two-pass prefix-suffix approach is our top choice for LeetCode 238 because it achieves O(n) time complexity without division, using only O(1) extra space beyond the output array. It’s elegant, efficient, and meets the problem’s ideal constraints, making it a standout solution.

How It Works

• First Pass (Prefix Products): Compute the product of all elements to the left of each index, storing it in the output array.
• Second Pass (Suffix Products): Multiply each output element by the product of all elements to its right, tracked on-the-fly.
• Result: Each position gets the product of all except itself.

Step-by-Step Example

Example 1: nums = [1,2,3,4]

• First Pass (Left to Right):
• output[0] = 1 (no left elements).
• output[1] = 1 (1).
• output[2] = 1*2 = 2.
• output[3] = 1*2*3 = 6.
• output = [1,1,2,6].
• Second Pass (Right to Left):
• Right product starts as 1.
• output[3] = 6 * 1 = 6, right = 4.
• output[2] = 2 * 4 = 8, right = 3*4 = 12.
• output[1] = 1 * 12 = 12, right = 2*12 = 24.
• output[0] = 1 * 24 = 24.
• output = [24,12,8,6].
• Output: [24,12,8,6].

Example 2: nums = [0,2]

• First Pass: [1,0].
• Second Pass: [2,0].
• Output: [2,0].

Code with Detailed Line-by-Line Explanation

Here’s the Python implementation:

Copy codeclass Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # Line 1: Initialize output array with prefix products
        n = len(nums)
        output = [1] * n

        # Line 2: First pass - prefix products
        for i in range(1, n):
            output[i] = output[i-1] * nums[i-1]  # Left product

        # Line 3: Second pass - multiply by suffix products
        right_product = 1
        for i in range(n-1, -1, -1):
            output[i] *= right_product  # Multiply by right product
            right_product *= nums[i]    # Update right product

        # Line 4: Return result
        return output

• Time Complexity: O(n) – two linear passes.
• Space Complexity: O(1) – only output array, no extra space.

Alternative Solution: Division-Based with Zero Handling

Why an Alternative Approach?

The division-based approach calculates the total product and divides by each element, handling zeros explicitly. It’s a simpler alternative if division is allowed, though it doesn’t meet the problem’s “no division” preference. It’s great for understanding the concept with minimal coding.

How It Works

• Compute the total product of all elements.
• Count zeros:
• If >1 zero, output is all zeros.
• If 1 zero, output is zero except at zero’s index (total product without zero).
• If no zeros, divide total by each element.

Step-by-Step Example

Example: nums = [1,2,3,4]

• Total = 1*2*3*4 = 24.
• No zeros: [24/1, 24/2, 24/3, 24/4] = [24,12,8,6].
• Output: [24,12,8,6].

Example: nums = [1,0,2]

• Total = 1*0*2 = 0.
• One zero at index 1:
• Product without zero = 1*2 = 2.
• Output = [0,2,0].
• Output: [0,2,0].

Code for Division-Based Approach

Copy codeclass Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # Line 1: Compute total product and count zeros
        total = 1
        zero_count = 0
        zero_index = -1
        for i, num in enumerate(nums):
            if num == 0:
                zero_count += 1
                zero_index = i
                if zero_count > 1:
                    return [0] * len(nums)  # More than 1 zero
            else:
                total *= num

        # Line 2: Build output
        output = [0] * len(nums)
        if zero_count == 1:
            output[zero_index] = total  # Product without zero
        elif zero_count == 0:
            for i in range(len(nums)):
                output[i] = total // nums[i]  # Divide total by each

        # Line 3: Return result
        return output

• Time Complexity: O(n) – two passes (product and output).
• Space Complexity: O(1) – excluding output.

Comparing the Two Solutions

• Best Solution (Two-Pass Prefix-Suffix):
• Pros: O(n) time, O(1) space, no division.
• Cons: Slightly more complex logic.
• Alternative Solution (Division-Based):
• Pros: Simple with division, intuitive.
• Cons: Uses division, less elegant for zero handling.

The prefix-suffix method is our best for meeting all constraints optimally.

Additional Examples and Edge Cases

All Zeros

• Input: [0,0]
• Output: [0,0] (multiple zeros).

Negative Numbers

• Input: [-1,-2]
• Output: [-2,-1].

Single Zero

• Input: [1,0]
• Output: [0,1].

Complexity Breakdown

• Prefix-Suffix:
• Time: O(n).
• Space: O(1).
• Division-Based:
• Time: O(n).
• Space: O(1).

Prefix-suffix excels without division.

Key Takeaways for Beginners

• Except Self: Product of all others.
• Prefix-Suffix: Combines left and right products.
• Division: Handles zeros carefully.
• Python Tip: Array manipulation—see [Python Basics](/python/basics).

Final Thoughts: Multiply Like a Pro

LeetCode 238: Product of Array Except Self in Python is a brilliant array challenge. The two-pass prefix-suffix solution offers a division-free masterpiece, while the division-based approach simplifies with zero handling. Want more array fun? Try LeetCode 152: Maximum Product Subarray or LeetCode 53: Maximum Subarray. Ready to compute? Head to Solve LeetCode 238 on LeetCode and multiply it out today!