Product of Array Except Self - Solution & Explanation
Problem Statement
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] <= 30- The product of any prefix or suffix of
numsis 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.)
Approach Overview
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 1: Prefix and Suffix Product Arrays
This approach involves calculating two additional arrays:
- Prefix Products: This array stores the product of all the elements to the left of each element in the original array.
- Suffix Products: This array stores the product of all the elements to the right of each element.
By multiplying the corresponding prefix and suffix product, we obtain the product of all other elements except the one at that given index.
The solution uses two auxiliary arrays for calculating prefixes and suffixes. The algorithm computes these in two separate for-loops and then calculates the result array in one final loop by multiplying appropriate elements of the prefix and suffix arrays.
Complexity
Time Complexity: O(n) since it involves three passes through the array.
Space Complexity: O(n) due to the two additional arrays used.
Approach 2: Single Array as Transformation
This approach optimizes space usage by performing the transformations directly on the output array. It first fills the output array with the left product transformation, then updates it with right products.
With the first pass, it calculates the products of elements to the left, and on the second pass, it adjusts for the products of elements to the right by maintaining a right product multiplier.
This C solution reverses the calculation order to incorporate right-side product values while maintaining a single result array.
Complexity
Time Complexity: O(n) due to linear pass transformations for left and right products.
Space Complexity: O(1) as no extra arrays are used, except for the output.
Approach 3: Two Passes
We define two variables left and right to represent the product of all elements to the left and right of the current element, respectively. Initially, left = 1 and right = 1. We define an answer array ans of length n.
First, we traverse the array from left to right. For the i-th element, we update ans[i] with left, then multiply left by nums[i].
Next, we traverse the array from right to left. For the i-th element, we update ans[i] to ans[i] times right, then multiply right by nums[i].
After the traversal, we return the answer array ans.
The time complexity is O(n), where n is the length of the array nums. Ignoring the space consumption of the answer array, the space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
PHP
Complexity Comparison
| Approach | Complexity |
|---|---|
| Prefix and Suffix Product Arrays | Time Complexity: O(n) since it involves three passes through the array. |
| Single Array as Transformation | Time Complexity: O(n) due to linear pass transformations for left and right products. |
| Two Passes | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Product of Array Except Self - Leetcode 238 - Python • NeetCode • 1,000,759 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Product of Array Except Self easy or hard?
Product of Array Except Self Python/Java solution
How to solve Product of Array Except Self in O(n)?
What is the best approach for Product of Array Except Self?
Is Product of Array Except Self asked at Google/Amazon/Meta?
What data structure is used in Product of Array Except Self?
What is the time complexity of Product of Array Except Self?
Ready to solve this problem?
Practice Product of Array Except Self with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor