Product of Array Except Self
No Division. O(n). Pure Logic.

Introduction

The Product of Array Except Self is one of those problems that looks simple on the surface but catches most beginners completely off guard — especially in live interviews. You are given an integer array and you need to return a new array where every position holds the product of all elements except the one at that position.

The catch? You cannot use division. That single constraint is what makes this go from trivial to genuinely tricky. Most people's first instinct is to multiply everything together and then divide by each element. Makes sense, right? But the moment there is a zero in the array, that whole approach falls apart.

If you have ever stared at this problem and felt stuck, this guide will walk you through every single step — from the brute force approach all the way to the space-optimized O(n) solution — with zero confusion.

Problem Statement

Examples

Input : [1, 2, 3, 4]
Output: [24, 12, 8, 6]

Why?
index 0 → 2×3×4 = 24
index 1 → 1×3×4 = 12
index 2 → 1×2×4 = 8
index 3 → 1×2×3 = 6

Input : [1, 2, 0, 4]
Output: [0, 0, 8, 0]

Why?
index 0 → 2×0×4 = 0
index 1 → 1×0×4 = 0
index 2 → 1×2×4 = 8  ← only position that skips the zero
index 3 → 1×2×0 = 0

Why This Problem Is Important

The product of array except self isn't just a puzzle — it teaches a mental model that appears everywhere in competitive programming and system design interviews.

Naive Approach — O(n²)

The brute force solution is simple: for each index, loop through the entire array and multiply everything except the current element.

def product_except_self_brute(nums):
    n = len(nums)
    output = [1] * n

    for i in range(n):
        product = 1
        for j in range(n):
            if i != j:
                product *= nums[j]
        output[i] = product

    return output

Division Approach — Why It's Wrong

The "smart" beginner approach: multiply all elements together, then divide by each element to get the product of the rest.

# This looks smart — but it's forbidden AND broken
def product_with_division(nums):
    total = 1
    for x in nums:
        total *= x

    # What if nums = [1, 2, 0, 4] → total = 0
    # output[2] = 0 / 0  →  ZeroDivisionError 💥
    return [total // x for x in nums]

Optimal Approach — Prefix + Suffix Product

Key Intuition

For any index i, the product of everything except itself is equal to:

output[i] = (product of all elements to the LEFT of i) × (product of all elements to the RIGHT of i)

So we precompute two arrays — left products and right products — then multiply them together. No division needed, ever.

def product_except_self(nums):
    n = len(nums)

    # Step 1: Build left product array
    # left[i] = product of all elements to the LEFT of index i
    left = [1] * n
    for i in range(1, n):
        left[i] = left[i - 1] * nums[i - 1]

    # Step 2: Build right product array
    # right[i] = product of all elements to the RIGHT of index i
    right = [1] * n
    for i in range(n - 2, -1, -1):
        right[i] = right[i + 1] * nums[i + 1]

    # Step 3: Multiply left and right at each index
    output = [left[i] * right[i] for i in range(n)]
    return output

Space Optimized — O(1) Extra Space

Instead of storing two separate arrays, we use the output array itself for left products, then do a reverse pass using a running suffix variable.

def product_except_self_optimized(nums):
    n = len(nums)
    output = [1] * n

    # Forward pass: store left products in output
    prefix = 1
    for i in range(n):
        output[i] = prefix
        prefix *= nums[i]

    # Backward pass: multiply with running suffix product
    suffix = 1
    for i in range(n - 1, -1, -1):
        output[i] *= suffix
        suffix *= nums[i]

    return output

# ──── Main (with user input) ────
if __name__ == "__main__":
    nums = list(map(int, input("Enter array elements: ").split()))
    result = product_except_self_optimized(nums)
    print("Output:", result)

Visualization — Prefix & Suffix Concept

For input [1, 2, 3, 4], here is exactly how the prefix and suffix products build up and combine:

Flowchart

Dry Run — Step by Step

Input: [1, 2, 3, 4]

Forward Pass (building prefix)

After forward pass: output = [1, 1, 2, 6]

Backward Pass (multiplying with suffix)

Final output: [24, 12, 8, 6] ✅

Time & Space Complexity

Test Cases

Edge Cases Deep Dive

Common Mistakes Beginners Make

Real-World Applications

Frequently Asked Questions

Conclusion

The Product of Array Except Self problem is a perfect example of how a constraint — no division — transforms a seemingly trivial task into something that teaches you a powerful algorithmic pattern.

The key insight is splitting the contribution of each index into two parts: everything on its left, and everything on its right. Build those products in two passes, multiply them together, and you're done in O(n) time with O(1) extra space.