Product of Array Except Self – Solution & Complexity

Q: What is the time and space complexity of Product of Array Except Self?

The optimal Product of Array Except Self solution runs in `O(n)` time and `O(1)` space. Multiply prefix products left-to-right, then suffix products right-to-left (output excluded from space).

Q: What is the most efficient way to solve Product of Array Except Self?

Multiply prefix products left-to-right, then suffix products right-to-left (output excluded from space). This gives `O(n)` time complexity, and is a classic arrays and prefix sum problem.

Q: How do you solve Product of Array Except Self in Python & JavaScript?

We provide a worked Product of Array Except Self solution in Python & JavaScript with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Product of Array Except Self an easy or hard interview question?

Product of Array Except Self is generally rated **Medium**. It tests arrays and prefix sum, which are common coding-interview patterns.

1. Understand Each Output Position

For each index i, the answer should be the product of every number except nums[i].
Division is not allowed, so we cannot compute one total product and divide by the current value.
The output order must match the input order exactly.

2. Consider the Brute Force Idea

For each index, multiply all values at every other index.
This is correct and handles zeroes, but it repeats almost the same multiplication for every position.
The nested loops make the time complexity O(n²).

def product_except_self(nums: list[int]) -> list[int]:
    answer = []
    for i in range(len(nums)):
        product = 1
        for j in range(len(nums)):
            if i != j:
                product *= nums[j]
        answer.append(product)
    return answer

3. Split the Product into Left and Right Parts

The product except self is the product of everything to the left times everything to the right.
A prefix pass can store products before each index.
A suffix pass can multiply in products after each index.

4. Fill Prefix Products First

Start with an answer array filled with 1.
Move left to right while carrying a running prefix product.
Before multiplying by nums[i], store the product of all values to the left in answer[i].

def product_except_self(nums: list[int]) -> list[int]:
    answer = [1] * len(nums)
    prefix = 1
    for i in range(len(nums)):
        answer[i] = prefix
        prefix *= nums[i]
    return answer

5. Final Solution and Complexity

The second pass moves right to left with a running suffix product.
Multiplying answer[i] by the suffix gives left product times right product, excluding nums[i] itself.
Time complexity is O(n), and extra space is O(1) besides the required output array.

def product_except_self(nums: list[int]) -> list[int]:
    answer = [1] * len(nums)

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

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

    return answer

Product of Array Except Self – Solution & Complexity

1. Understand Each Output Position

2. Consider the Brute Force Idea

3. Split the Product into Left and Right Parts

4. Fill Prefix Products First

5. Final Solution and Complexity

FAQ

What is the time and space complexity of Product of Array Except Self?

What is the most efficient way to solve Product of Array Except Self?

How do you solve Product of Array Except Self in Python & JavaScript?

Is Product of Array Except Self an easy or hard interview question?