MediumArrayPrefix SumUpdated Sep 2026

238. Product of Array Except Self

Asked at Google, Meta, Amazon, Microsoft and 5 more

Difficulty

Medium

Time

O(n)

Space

O(1) extra

Pattern

Array

Companies

9

Problem

You are given an integer array nums. Build a new array answer of the same length, where answer[i] is the product of every element of nums except nums[i].

Two rules make this harder than it looks. First, you may not use division — so you cannot just multiply everything together and divide by nums[i]. Second, the whole thing must run in O(n) time, meaning a single pass or two, not a nested loop.

The array can contain zeros and negative numbers, and the answer for each position is guaranteed to fit in a 32-bit integer. The output array does not count toward extra space, so you can build the answer in place.

Each answer skips one element

nums12340123To fill answer[0], ignore nums[0] and multiply 2×3×4 =24.answer2412860123Each slot holds the product of everything except thenumber at the same index.
For nums = [1,2,3,4], answer[i] is the product of all the other three numbers.

Constraints

  • ●2 <= nums.length <= 10^5
  • ●-30 <= nums[i] <= 30
  • ●answer[i] is guaranteed to fit in a 32-bit integer
  • ●Division is not allowed
  • ●The algorithm must run in O(n) time

Examples

Example 1
Inputnums = [1,2,3,4]
Output[24,12,8,6]
WhyFor index 0 we multiply 2×3×4 = 24. For index 1 we multiply 1×3×4 = 12. For index 2 we multiply 1×2×4 = 8. For index 3 we multiply 1×2×3 = 6.
Example 2
Inputnums = [-1,1,0,-3,3]
Output[0,0,9,0,0]
WhyThere is one zero, at index 2. Every position except index 2 includes that zero in its product, so those answers are 0. Index 2 skips the zero, so its answer is (-1)×1×(-3)×3 = 9.

Asked At

9 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
NetflixMediumView all Netflix questions →
UberMediumView all Uber questions →
AtlassianMediumView all Atlassian questions →
WalmartMediumView all Walmart questions →

How to Think About It

1

The product of all except nums[i] = (product of all to the left of i) × (product of all to the right of i).

2

First pass (left to right): result[i] = product of all elements to the left of i. This is a prefix product.

3

Second pass (right to left): multiply result[i] by the product of all elements to the right of i. This is a suffix product.

4

You can do it in one output array by using the result array for prefix products, then a running suffix variable for the second pass.

5

Why no division: division by zero is undefined, and the problem explicitly forbids it. The two-pass approach avoids division entirely.

6

Edge cases: single element (return [1]), zero in array (still works since we don't divide).

Optimal Approach

Step 1: Create result array of size n, fill with 1.
Step 2: Left pass — prefix = 1. For i from 0 to n-1:
result[i] = prefix
prefix *= nums[i]
Step 3: Right pass — suffix = 1. For i from n-1 down to 0:
result[i] *= suffix
suffix *= nums[i]
Step 4: Return result.

The left pass stores the product of everything to the left. The right pass multiplies by the product of everything to the right.

Time: O(n). Space: O(1) extra (output array not counted).

Left products then right products

result after left pass11260123result[i] = product of nums[0..i-1]; result[3] = 1×2×3= 6.result after right pass2412860123Walking right to left, multiply each slot by therunning suffix product: 1×24 = 24 at index 0.left pass: result[i] = prefix; prefix *= nums[i]right pass: result[i] *= suffix; suffix *= nums[i]answer[i] = left product × right product
Pass 1 writes the product of everything to the left. Pass 2 multiplies in the product of everything to the right.
ComplexityTime O(n)Space O(1) extraTwo linear passes over the array; the only extra memory is a couple of running product variables, since the output array is not counted.

What Trips People Up in Real Interviews

1

Using division. The problem explicitly forbids it, and it doesn't handle zeros correctly.

2

Confusing "product of all except self" with "product of all." You need to exclude the current element.

3

Not handling zeros. If there are two or more zeros, the result is all zeros. If there's one zero, all positions except that one are zero.

4

Forgetting to initialize the result array to 1, not 0. Multiplying by 0 gives 0.

5

Using two separate arrays for prefix and suffix products. You can do it in one output array plus a single running variable — no need for extra O(n) space.

Solution Code

O(n) time
def productExceptSelf(nums):
    n = len(nums)
    result = [1] * n
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Product of Array Except Self problem?

Given an integer array `nums`, return an array answer such that `answer[i]` is the product of all the elements of `nums` except `nums[i]`. You must solve it without using division and in `O(n)` time.

How do you solve Product of Array Except Self?

The optimal approach runs in O(n) time and O(1) extra space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Product of Array Except Self?

Product of Array Except Self is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian, Walmart. It is a medium difficulty problem.

What are common mistakes on Product of Array Except Self?
  • Using division. The problem explicitly forbids it, and it doesn't handle zeros correctly.
  • Confusing "product of all except self" with "product of all." You need to exclude the current element.
  • Not handling zeros. If there are two or more zeros, the result is all zeros. If there's one zero, all positions except that one are zero.
  • Forgetting to initialize the result array to 1, not 0. Multiplying by 0 gives 0.
  • Using two separate arrays for prefix and suffix products. You can do it in one output array plus a single running variable — no need for extra `O(n)` space.