Problem

Given an integer array nums, return an array output where:

output[i] = product of all elements in nums except nums[i]

The follow-up asks us to solve it in O(n) time without using division.

Example 1

Input: nums = [1, 2, 4, 6]
Output: [48, 24, 12, 8]

Example 2

Input: nums = [-1, 0, 1, 2, 3]
Output: [0, -6, 0, 0, 0]

Brute Force Approach

The simplest idea is to calculate the product for every index by looping through the whole array and skipping the current index.

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = []

        for i in range(len(nums)):
            product = 1

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

            res.append(product)

        return res

Complexity

• Time: O(n²)
• Space: O(1) extra space, excluding the output array

This works, but it is too slow because for every element, we loop through the entire array again.

Better Approach: Prefix and Suffix Arrays

For each index, we can split the product into two parts:

product except self = product of elements before it * product of elements after it

So we create:

• prefix[i]: product of all numbers before index i
• suffix[i]: product of all numbers after index i

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)

        prefix = [0] * length
        suffix = [0] * length
        res = [0] * length

        prefix[0] = 1
        suffix[length - 1] = 1

        for i in range(1, length):
            prefix[i] = nums[i - 1] * prefix[i - 1]

        for i in range(length - 2, -1, -1):
            suffix[i] = nums[i + 1] * suffix[i + 1]

        for i in range(length):
            res[i] = prefix[i] * suffix[i]

        return res

Example

For:

nums = [1, 2, 4, 6]

The prefix array becomes:

[1, 1, 2, 8]

The suffix array becomes:

[48, 24, 6, 1]

Multiplying both arrays:

[1 * 48, 1 * 24, 2 * 6, 8 * 1]

Gives:

[48, 24, 12, 8]

Complexity

• Time: O(n)
• Space: O(n)

This is much better than brute force, but we can still optimize the space.

Optimized Approach: Using Only the Result Array

Instead of creating separate prefix and suffix arrays, we can store the prefix products directly in res.

Then, we traverse from the right side and multiply each index by the suffix product.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1] * len(nums)

        prefix = 1
        for i in range(len(nums)):
            res[i] = prefix
            prefix *= nums[i]

        suffix = 1
        for i in range(len(nums) - 1, -1, -1):
            res[i] *= suffix
            suffix *= nums[i]

        return res

How It Works

First pass:

res[i] = product of everything before nums[i]

Second pass:

res[i] *= product of everything after nums[i]

This gives the final product except self.

Walkthrough

For:

nums = [1, 2, 4, 6]

After the prefix pass:

res = [1, 1, 2, 8]

Then we go from right to left and multiply by suffix values:

res = [48, 24, 12, 8]

Final Complexity

• Time: O(n)
• Space: O(1) extra space, excluding the output array

Key Idea

The main trick is realizing that for each index, we need:

left product * right product

By doing one pass from the left and one pass from the right, we can calculate the answer without using division and without needing nested loops.