Watch 10 video solutions for Product of Array Except Self, a medium level problem involving Array, Prefix Sum. This walkthrough by NeetCode has 948,316 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
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]
Example 2:
Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 105-30 <= nums[i] <= 30nums is guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
Problem Overview: You are given an integer array nums. For each index i, compute the product of every element in the array except nums[i]. The catch: you cannot use division and the solution must run in linear time.
Approach 1: Prefix and Suffix Product Arrays (O(n) time, O(n) space)
This approach builds two helper arrays. The prefix array stores the product of all elements to the left of each index, while the suffix array stores the product of elements to the right. Iterate from left to right to fill prefix values, then iterate from right to left to compute suffix values. The result for each index is simply prefix[i] * suffix[i]. This works because the prefix holds the product before the index and the suffix holds the product after it.
The technique resembles patterns used in prefix sum problems, but instead of cumulative sums you maintain cumulative products. Time complexity is O(n) since the array is traversed a constant number of times, and space complexity is O(n) due to the two auxiliary arrays. This version is easy to reason about and useful when first learning the pattern.
Approach 2: Single Array as Transformation (O(n) time, O(1) extra space)
This optimized solution removes the need for a separate suffix array. First, build prefix products directly inside the output array. Initialize result[0] = 1, then iterate forward so each position stores the product of all elements before it. Next, iterate from right to left while maintaining a running suffix product variable. Multiply the stored prefix value with the current suffix product and update the suffix as you go.
The key insight: the output array already contains the prefix product, so you only need a single variable to track the suffix product during the backward pass. This reduces auxiliary space while still performing two linear scans. Time complexity remains O(n), while extra space becomes O(1) (excluding the output array). The technique is common in array transformation problems where intermediate results can be reused.
Recommended for interviews: Interviewers usually expect the single-array prefix + running suffix solution. Showing the prefix/suffix array idea first demonstrates understanding of the decomposition, but the optimized version proves you can reduce memory usage while maintaining linear time. That combination signals strong problem-solving skills in array and cumulative computation patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix and Suffix Product Arrays | O(n) | O(n) | When learning the pattern or when clarity matters more than memory usage |
| Single Array Transformation (Prefix + Running Suffix) | O(n) | O(1) extra space | Preferred interview solution and optimal for memory‑constrained scenarios |