Product of Array Except Self
Understanding the Problem
At each index i, we need the product of every element in the array except the one at position i. The no-division constraint rules out computing the total product once and dividing by nums[i]. That shortcut also fails when the array contains a zero, since dividing by zero is undefined and a single zero would make the total product zero for every other index too.
The product of all elements except nums[i] is the product of two sub-ranges:
- The product of everything to the left of index
i - The product of everything to the right of index
i
This prefix-suffix decomposition drives every efficient solution below. Computing these left and right products for every index gives the answer without any division.
Key Constraints:
2 <= nums.length <= 10^5→ With up to 100,000 elements, an O(n^2) brute force performs around 10^10 operations and exceeds the time limit. The problem also explicitly requires O(n) time.- The cumulative product of any prefix or suffix is guaranteed to fit in a 32-bit integer, so
intarithmetic is safe and nolongis needed. - No division allowed → The answer must be built using only multiplication.
- Follow-up: O(1) extra space → The output array does not count, so the goal is to avoid allocating additional arrays.
Approach 1: Brute Force
Intuition
Compute each answer independently. For each index i, loop through the entire array and multiply together every element whose index is not i. This follows directly from the definition of the problem and produces a correct result, but it repeats most of its work.
Algorithm
- Create a result array of the same length as
nums. - For each index
i, iterate through the entire array. - Multiply together every element where the index is not
i. - Store the product in
result[i]. - Return the result array.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each of the n elements, we iterate through all n elements to compute the product. That's n * n = O(n^2) operations.
- Space Complexity: O(1) extra space. We only use the output array, which doesn't count as extra space per the problem statement.
Computing answer[i] and answer[i+1] repeats almost the same multiplication, since the two products differ only by which single element they exclude. The next approach removes that repetition by precomputing the left and right products once.
Approach 2: Prefix and Suffix Products
Intuition
The product of all elements except nums[i] splits into two parts:
- Prefix product: The product of all elements before index
i - Suffix product: The product of all elements after index
i
Both can be built in O(n) time. A left-to-right pass accumulates the prefix products, and a right-to-left pass accumulates the suffix products. The answer at each index is then prefix[i] * suffix[i].
prefix[i] is defined to cover indices 0..i-1 and suffix[i] to cover indices i+1..n-1. Neither includes nums[i], and together they cover every other index exactly once. Their product is therefore the product of all elements except nums[i]. The boundary values prefix[0] = 1 and suffix[n-1] = 1 represent an empty range, which correctly contributes a factor of 1.
Algorithm
- Create a
prefixarray whereprefix[i]holds the product of all elements before indexi. - Build it left-to-right: start with
prefix[0] = 1, thenprefix[i] = prefix[i-1] * nums[i-1]. - Create a
suffixarray wheresuffix[i]holds the product of all elements after indexi. - Build it right-to-left: start with
suffix[n-1] = 1, thensuffix[i] = suffix[i+1] * nums[i+1]. - The answer at each index is
prefix[i] * suffix[i].
Example Walkthrough
Code
- Time Complexity: O(n). Three separate passes through the array, each O(n). Total: O(3n) = O(n).
- Space Complexity: O(n). We use two extra arrays (
prefixandsuffix) of size n. The output array doesn't count as extra space per the problem statement.
This achieves O(n) time but uses two auxiliary arrays of size n. The next approach removes both by storing the prefix products directly in the output array and replacing the suffix array with a single running variable.
Approach 3: Optimized (Single Output Array)
Intuition
The two extra arrays from the previous approach are never both needed at full size. The output array can hold the prefix products after a first pass. A second pass then walks right to left, multiplying each entry by a running suffix product that is updated as it moves. This replaces the suffix array with a single variable, since only its current value is ever read.
Algorithm
- Store prefix products directly in the result array (left-to-right pass).
- Initialize a variable
suffixProduct = 1. - Traverse right-to-left, multiplying each
result[i]bysuffixProduct. - After multiplying, update
suffixProductby multiplying it withnums[i]. - Return the result array.
After the first pass, result[i] holds the product of all elements to the left of index i. In the second pass, suffixProduct is multiplied into result[i] before it is updated with nums[i]. So at the moment of the multiply, suffixProduct equals the product of indices i+1..n-1 only, never including nums[i]. Combining the stored left product with this right product leaves each position holding the product of every element except itself. The ordering of the two lines inside the loop is what keeps nums[i] out of its own answer.
Example Walkthrough
Code
- Time Complexity: O(n). Two passes through the array, each O(n). Total: O(2n) = O(n).
- Space Complexity: O(1) extra space. We only use one extra variable (
suffixProduct). The output array doesn't count as extra space per the problem statement.