Product of Array Except Self

Return an array where each element is the product of all other elements.

Pattern

Prefix/Suffix Product

This problem follows the Prefix/Suffix Product pattern, commonly found in the Arrays & Hashing category. Recognizing this pattern is key to solving it efficiently in an interview setting.

Approach

How to Solve It

Two passes: build prefix products left-to-right, then suffix products right-to-left.

Key Insight

Two passes replace division — the prefix pass captures everything to the left, the suffix pass captures everything to the right.

Step-by-step

1Initialize result array with all 1s
2First pass (left to right): multiply each position by running prefix product
3Second pass (right to left): multiply each position by running suffix product
4Each position now contains the product of everything except itself

Pseudocode

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

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)

More Arrays & Hashing Problems

EasyContains DuplicateHash Set EasyValid AnagramFrequency Count EasyTwo SumHash Map Lookup MediumGroup AnagramsHash Map Grouping MediumTop K Frequent ElementsBucket Sort / Heap

Master this pattern with YeetCode

Practice Product of Array Except Self and similar Arrays & Hashing problems with flashcards. Build pattern recognition through active recall.

Practice this problem

Previous← Top K Frequent Elements NextEncode and Decode Strings →