DSA AnimatorDSA animations
Product of Array Except Self LC #238 Medium Array
Problem

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all elements of nums except nums[i]. You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Explanation: 24=2×3×4, 12=1×3×4, 8=1×2×4, 6=1×2×3
Example 2
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints: 2 ≤ nums.length ≤ 105; -30 ≤ nums[i] ≤ 30; The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. O(1) extra space (output array does not count).
Try Examples
Custom:
Approach
Prefix × Suffix Products
Four views: original nums, prefix (left products), suffix (right products), then final = prefix × suffix. Same O(n) two-pass idea — no division.
Four Arrays
prefix
original
suffix
final
nums (input) prefix = product left of i suffix = product right of i final = prefix × suffix
Variables
Phase
—
i
—
running
—
at i
—
Step Logic
Press ▶ Play or Next Step to begin.
✅
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Build prefix[]: prefix[0]=1, then prefix[i]=prefix[i−1]×nums[i−1] (L→R)
2
Build suffix[] with running product (R→L); set final[i]=prefix[i]×suffix[i]
3
Return final[] — same as in-place ans[] trick, shown as 4 arrays for clarity
Time
O(n)
Space
O(1) extra
Why It Works

At index i, exclude nums[i] and multiply everything else: left part × right part. prefix[i] stores the left product, suffix[i] the right product, and final[i] is their product. The code reuses one array instead of three — we show all four rows so each piece is visible.

How to solve Product of Array Except Self

LeetCode 238 · Medium · Arrays · Pattern: Prefix & Suffix

Why the obvious approach is slow

Multiplying everything and dividing breaks on zeros, and division is not allowed anyway. Recomputing the product for every index is O(n²).

The key idea

Split it in two: the product of everything on the left, times the product of everything on the right. Build the left products in one pass, and multiply in the right products in a second pass.

Remember

Product except self equals left product times right product. Two passes, and the answer array doubles as storage.

Run the animation above on your own input, or watch the 1:37 video explanation of Product of Array Except Self with a dry run and Java code.

More Arrays problems