Product of Array Except Self
Last Updated: April 2, 2026
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 the tempting approach of computing the total product and dividing by nums[i] (which would also break for zeros).
So how do we get the product of everything except nums[i] without division? Think about it this way: the product of all elements except nums[i] is really just two things multiplied together:
- The product of everything to the left of index
i - The product of everything to the right of index
i
This prefix-suffix decomposition is the key insight. If we can efficiently compute these left and right products for every index, we're done.
Key Constraints:
2 <= nums.length <= 10^5→ With up to 100,000 elements, we need O(n) time (the problem explicitly demands it). An O(n^2) brute force will TLE.-30 <= nums[i] <= 30→ Small values, so individual products won't overflow. But the cumulative product across many elements is guaranteed to fit in a 32-bit integer by the problem statement.- No division allowed → This eliminates the obvious "compute total product and divide" shortcut. We must build the answer using only multiplication.
- Follow-up: O(1) extra space → The output array doesn't count, so we need to avoid creating additional arrays.
Approach 1: Brute Force
Intuition
The most direct approach: for each index i, loop through the entire array and multiply every element except nums[i]. No tricks, no cleverness, just brute computation.
This is what most people think of first, and it works. It's just slow.
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.
This approach works but recomputes nearly identical products for every index. What if we precomputed the product of all elements to the left and to the right of each index, so we could combine them in O(1)?
Approach 2: Prefix and Suffix Products
Intuition
The brute force recomputes almost the same product over and over. When computing answer[3], we multiply everything except nums[3]. When computing answer[4], we multiply everything except nums[4]. Those two products share almost all their terms.
Here's the observation that changes everything: the product of all elements except nums[i] can be split into two parts:
- Prefix product: The product of all elements before index
i - Suffix product: The product of all elements after index
i
We can build both arrays in O(n) time with simple left-to-right and right-to-left passes. Then answer[i] = prefix[i] * suffix[i].
The prefix array captures the cumulative product of all elements to the left of each index. The suffix array captures the cumulative product of all elements to the right. When we multiply them together, we get the product of everything except the element at that index, because prefix[i] skips nums[i] (it only goes up to i-1) and suffix[i] also skips nums[i] (it starts from i+1).
This eliminates all redundant computation. Instead of recalculating nearly identical products for each index, we compute two running products and combine them.
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 approach achieves O(n) time but uses two auxiliary arrays of size n. What if we stored the prefix products directly in the output array and replaced the suffix array with a single running variable?
Approach 3: Optimized (Single Output Array)
Intuition
The prefix-suffix approach uses two extra arrays. But notice something: we don't actually need to store both arrays simultaneously. We can use the output array itself to store the prefix products first, and then do a single right-to-left pass where we multiply in the suffix products on the fly using a running variable.
This is a classic space optimization technique: replace an array with a single variable when you only need the running value.
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. During the second pass, suffixProduct accumulates the product of all elements to the right of the current index. When we multiply result[i] *= suffixProduct, we're combining the left product (already stored) with the right product (carried in the variable). By the time we're done, each position holds exactly what we need: the product of everything except itself.
The key insight is that we don't need the entire suffix array at once. We only ever need the current suffix product value, so a single variable suffices.
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.