← DSA Atlas
Dedicated problem page · #238

Product of Array Except Self

MediumArrays and HashingPrefix and suffix productsPrefix/suffix accumulation
Solve on LeetCode ↗
238
MediumArrays and HashingPrefix/suffix accumulationPrefix and suffix products

Product of Array Except Self

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

Open official problem prompt ↗
In plain English

Produce, for each position, the product of the whole array with that one element left out — cheaply and without dividing.

Picture it like this

Two people count a line of runners: one walks left to right recording how many are ahead of each runner, the other walks right to left recording how many are behind. Multiply the two tallies at each runner to know everyone but themselves.

Example
Input
nums = [1, 2, 3, 4]
Output
[24, 12, 8, 6]
Why
answer[0]=2*3*4=24, answer[1]=1*3*4=12, answer[2]=1*2*4=8, answer[3]=1*2*3=6.
Constraints
2 <= nums.length <= 10^5-30 <= nums[i] <= 30The product of any prefix or suffix of nums fits in a 32-bit integerDivision operator is not allowed
Pattern lesson

See the pattern, then code

Prefix and suffix products
Recognition clue

Each output depends on everything except one position, and division is banned — that points to combining a running product from the left with one from the right.

↗
Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. The product excluding index i equals (product of everything to its left) times (product of everything to its right). Both can be swept in linear time and multiplied together.

New words, made simpleKnow these before the algorithm
Prefix product
The product of all elements before a given index.
Suffix product
The product of all elements after a given index.
In-place output
Reusing the returned array to hold intermediate results, keeping extra space at O(1).
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Divide total product

Forbidden by the prompt and breaks when any element is 0 (division by zero / ambiguity).

Compute the full product and divide by nums[i] for each i.

Time O(n)Space O(1)
Two auxiliary arrays

Correct and clear but uses extra linear space.

Store prefix products and suffix products in separate arrays, then multiply.

Time O(n)Space O(n)
Best choicePrefix then suffix in the output

Optimal; only the output array plus two running scalars.

Write left products into answer, then fold in right products with a single scalar.

Time O(n)Space O(1)
The rule we keep true

Invariant

After the first pass answer[i] holds the product of nums[0..i-1]; during the second pass, when index i is processed, the scalar suffix holds the product of nums[i+1..n-1].

Why this is correct

Reasoning

By definition the product excluding i is (nums[0..i-1]) * (nums[i+1..n-1]). The forward pass deposits the left factor into answer[i], and the backward pass multiplies in the right factor exactly once, so each answer[i] becomes the full excluded product.

The algorithm in three movesSay these aloud before coding
1Fill answer[i] with the product of all elements strictly to the left, using a running prefix

after prefix pass: answer = [1, 1, 2, 6]

2Sweep from the right with a running suffix product

suffix pass at i=2: answer[2] = 2 * 4 = 8

3Multiply each answer[i] by the suffix so far, then extend the suffix

final: [24, 12, 8, 6]

4Return answer

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
32
43
1 · Readnums
2 · Askleft product before i?
3 · Update stateprefix runs 1,1,2,6
4 · Resultanswer = [1, 1, 2, 6]
Key takeaway

For index 2, prefix product (1*2=2) times suffix product (4) gives 8.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Setup

    answer starts as all 1s so the first prefix write (1) is a correct empty-left product.

  2. 2
    Lines 5-8Forward prefix pass

    Write the current prefix into answer[i] first, then fold nums[i] into prefix for the next index.

  3. 3
    Lines 9-12Backward suffix pass

    Multiply each cell by the running right-side product, then extend that product leftward.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Exactly one zero: every answer is 0 except at the zero's index
  • Two or more zeros: the whole answer array is 0
  • Negative values flipping the sign of products
!

Common beginner mistakes

  • Trying to divide by the total product, which fails on zeros and is disallowed
  • Counting the output array against the O(1) space claim — only auxiliary space is counted
  • Off-by-one on the prefix write: you must store the prefix before multiplying nums[i] in, so index i excludes itself
Check your understanding

Why does storing prefix into answer[i] before multiplying nums[i] guarantee index i is excluded?

More in Arrays and Hashing

#1Two SumComplement lookup#49Group AnagramsCanonical key bucketing#128Longest Consecutive SequenceSequence-start expansion#560Subarray Sum Equals KPrefix-sum complement count#36Valid SudokuConstraint tracking with sets#41First Missing PositiveIndex-as-hash placement (cyclic sort)