Product of Array Except Self

Product of Array Except Self

What is this problem about?

The Product of Array Except Self problem asks you to return an array where each element is the product of all other elements in the input array, without using division and in O(n) time. This Product of Array Except Self coding problem is a classic prefix-product problem demonstrating the "left product × right product" technique. The array and prefix sum interview pattern is directly demonstrated.

Why is this asked in interviews?

Apple, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, Adobe, and dozens more ask this because it's one of the most commonly asked medium problems. It validates O(n) thinking without division and tests prefix array precomputation — a skill that appears in many other problems.

Algorithmic pattern used

Left prefix product × right suffix product. Build left[i] = product of all elements before index i. Build right[i] = product of all elements after index i. Result ans[i] = left[i] * right[i]. Space-optimize: compute left pass into ans, then multiply by running right product from right to left.

Example explanation

arr=[2,3,4,5]. Left products: [1,2,6,24]. Right products: [60,20,5,1]. ans = [160, 220, 65, 241] = [60,40,30,24].

Space-optimized: ans=[1,2,6,24] after left pass. right=1. Scan right: ans[3]=1=24, right=5. ans[2]=5=30, right=20. ans[1]=20=40, right=60. ans[0]=60=60. Result: [60,40,30,24] ✓.

Common mistakes candidates make

• Using division (not allowed; also fails when zeros exist).
• Not handling zeros (zero in array makes some products 0).
• O(n²) brute force (compute product for each element separately).
• Incorrect direction in the right pass (must go right to left).

Interview preparation tip

Product of Array Except Self is the quintessential prefix array problem. Master the two-pass approach: left pass computes prefix products, right pass multiplies by suffix products. The O(1) extra space version is impressive: use the output array for left products, then a single variable for running right product. This exact pattern — "left contribution × right contribution" — appears in "trapping rain water," "maximum width ramp," and "sum of array elements except self."