Day 2 of solving LeetCode problems to prepare for FAANG/MAANG interviews.

Meta:

• Title: Product of Array Except Self — Brute Force & Efficient O(n) Approach (Python)
• Slug: product-of-array-except-self
• Description: A step-by-step guide that covers the brute-force approach, the optimized prefix/suffix O(n) solution without division, Python code, complexity analysis, edge cases and test cases — ready to publish on your blog or website.

---

Introduction

The Product of Array Except Self is a common interview problem that tests your ability to reason about products and efficiencies without relying on division. The task is simple to state but requires careful thinking to meet constraints: no division and O(n) time.

This article covers:

• Problem statement and examples
• A naive (brute-force) solution and why it’s not ideal
• The optimal two-pass prefix/suffix solution in O(n) time and O(1) extra space (excluding output)
• Python implementations for both approaches
• Edge cases, test cases, and explanations suitable for publishing on your site.

---

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].

Constraints:

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums fits in a 32-bit integer.
• Do not use division.
• The algorithm must run in O(n) time.

Examples

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]

---

Brute-force Approach (Intuitive)

Idea

For each index i, multiply all elements except nums[i] by looping through the array and skipping i. This is the most straightforward approach.

Complexity

• Time: O(n^2) — for each of the n indices we potentially multiply up to n-1 elements.
• Space: O(n) — for the output array.

Python Implementation (Brute-force)

def product_except_self_bruteforce(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [1] * n
    for i in range(n):
        prod = 1
        for j in range(n):
            if i == j:
                continue
            prod *= nums[j]
        result[i] = prod
    return result

# Example
print(product_except_self_bruteforce([1, 2, 3, 4]))  # [24, 12, 8, 6]

When is brute-force acceptable?

• Small input sizes (e.g., n <= 1000) where performance is not critical.
• When you need to prototype quickly or explain the simplest correct solution in an educational setting.

However, interviews and production code require better performance, so we move to the optimized approach.

---

Optimized Approach — Prefix & Suffix Products (O(n))

Key Insight

For every index i, the answer is the product of everything to the left of i times the product of everything to the right of i:

answer[i] = (product of nums[0..i-1]) * (product of nums[i+1..n-1])

We can compute left products in one left-to-right pass and then incorporate right products in a right-to-left pass, using only constant extra space (besides the output array).

Complexity

• Time: O(n) — two linear passes.
• Space: O(1) extra space (ignoring the output array which is required). We use result to store intermediate left products.

Python Implementation (Optimized)

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    # result holds the prefix products initially
    result = [1] * n

    # Left pass: result[i] will be product of elements to the left of i
    left_product = 1
    for i in range(n):
        result[i] = left_product
        left_product *= nums[i]

    # Right pass: multiply with suffix products on the fly
    right_product = 1
    for i in range(n - 1, -1, -1):
        result[i] *= right_product
        right_product *= nums[i]

    return result

# Example tests
print(product_except_self([1, 2, 3, 4]))        # [24, 12, 8, 6]
print(product_except_self([-1, 1, 0, -3, 3]))  # [0, 0, 9, 0, 0]

Why this handles zeros correctly

• If an array has one zero, every position except the zero’s index will include that zero in its product, producing 0. The zero index’s product equals the product of all non-zero elements (computed via left and right products).
• If there are two or more zeros, every index’s product will be 0 because every product excludes at most one element but still includes at least one zero.

---

Alternative (Counting Zeros) — Another O(n) approach

You can also solve this using a single pass by counting zeros and computing the total product of non-zero elements.

Logic

• Count the number of zeros in the array.
• Compute the product of all non-zero elements.
• If zeros >= 2: every output is 0.
• If zeros == 1: the output is 0 for all indices except the index of zero, which is the product of non-zero elements.
• If zeros == 0: output[i] = total_product // nums[i] — but since division is not allowed, this method is more of a conceptual alternative; you should avoid division if the problem forbids it.

This method can be used when you are allowed to use division or if you only want a constant-time per-index after precomputation and handle zeros carefully.

---

Edge Cases & Notes

1. Zeros: Covered above. One zero vs multiple zeros differ.
2. Negative numbers: Signs are handled naturally by multiplication.
3. Large arrays: Use the O(n) method. The brute-force approach will time out or be slow.
4. 32-bit guarantee: The problem guarantees products of prefixes/suffixes will fit in 32-bit signed integer ranges for test inputs. If implementing for arbitrary inputs, consider big integers or checks for overflow.

---

Tests (Additional)

# random tests
print(product_except_self([5, 0, 2]))     # [0, 10, 0]
print(product_except_self([2, 3]))        # [3, 2]
print(product_except_self([1, -1, 1]))    # [-1, 1, -1]

---

Final Thoughts

This problem is a great exercise in transforming an obvious but slow solution into a fast, memory-efficient one by reusing the output array as temporary storage and performing two linear passes. The prefix/suffix technique is widely applicable to other problems that combine information from both sides of an index.

---