Product of Array Except Self - Solution & Explanation

Problem Overview: Given an integer array nums, build a new array where each position i contains the product of every element in the array except nums[i]. The constraint that makes this problem interesting: you cannot use division, and the solution must run in linear time.

The key observation is that the product for index i is simply the product of all elements to its left multiplied by the product of all elements to its right. Once you separate the array into prefix products and suffix products, the solution becomes straightforward.

Approach 1: Prefix and Suffix Product Arrays (Time: O(n), Space: O(n))

Create two auxiliary arrays: prefix and suffix. The prefix[i] value stores the product of all elements before index i, computed by iterating from left to right. The suffix[i] value stores the product of all elements after index i, computed by iterating from right to left. Once both arrays are built, the answer at position i becomes prefix[i] * suffix[i]. This approach is easy to reason about and clearly separates the logic for left and right products. Time complexity is O(n) because the array is scanned three times, and space complexity is O(n) for the extra arrays.

This technique frequently appears in problems involving cumulative values across an array or partial computations similar to prefix sum patterns, except multiplication replaces addition.

Approach 2: Single Array as Transformation (Time: O(n), Space: O(1) extra)

The optimal solution eliminates the explicit suffix array. First, iterate from left to right and store prefix products directly in the result array. At index i, store the product of all elements before it. Then traverse the array from right to left while maintaining a running variable that represents the suffix product. Multiply the current result value by this running suffix product, then update the suffix by multiplying it with nums[i]. Each element is processed twice, but no additional arrays are required.

The insight is that you do not need to store every suffix product—only the current cumulative value while scanning from the end. Time complexity remains O(n), while extra space drops to O(1) excluding the output array. This pattern—computing prefix values and updating them with a reverse pass—appears in many array transformation problems.

Recommended for interviews: The single-array transformation approach is what interviewers expect. The prefix/suffix array method shows you understand the decomposition of the problem, but the optimized version demonstrates awareness of space optimization and in-place computation patterns. Writing the prefix logic first and then layering the reverse suffix pass is usually the cleanest way to derive the optimal solution during an interview.