Product Except Self — Problem Statement & Solution Guide
Problem Description
Given an array of integers, return an array where each element at index i is the product of all the numbers in the input array except the number at index i.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Product Except Self"
WHY DOES IT MATTER?
The product‑except‑self pattern exemplifies how to replace nested loops with linear scans by precomputing cumulative information, a technique that recurs in many array‑based problems such as range sums, sliding windows, and histogram calculations.
OPTIMIZATION CHALLENGE
The breakthrough is realizing that the product for index i can be split into two independent components—left product and right product—each of which can be built incrementally in a single pass, thus collapsing the quadratic work into linear time.
REAL-WORLD CONNECTION
Think of a distributed data pipeline where each node needs to know the aggregate of all other nodes' metrics except its own; prefix‑suffix aggregation lets each node compute its answer locally after two broadcast phases, avoiding O(N²) pairwise communication.
During an interview, compute the left‑product array in place, then reuse the output array to accumulate the right‑product on the fly; this shows you understand space‑optimal tricks and can think on the fly.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The naive solution multiplies all elements for each index, leading to O(n²) time, which quickly becomes infeasible for large n (e.g., n = 10⁵). The optimal paradigm leverages prefix and suffix products: for each position i we can compute the product of all elements to its left (prefix) and all elements to its right (suffix) in linear passes. By storing the prefix product while iterating forward and the suffix product while iterating backward, we can combine them to obtain the final result without ever multiplying the element at i itself. This approach reduces the problem to two linear traversals and eliminates the need for division, preserving correctness even when zeros are present in the input array.
Interview Questions on This Problem
Q1How would you modify the algorithm if division were allowed and the array contained no zeros?
Compute the total product of all elements in one pass, then for each index i return totalProduct / nums[i]. This runs in O(n) time and O(1) extra space, but you must guard against division by zero and integer overflow.
Q2Explain how you would adapt the solution to work with a stream of numbers where you cannot store the entire array in memory.
Maintain two rolling aggregates: a prefix product as you read forward and a suffix product using a second pass after buffering the stream into a temporary storage (or using a two‑pointer technique with a circular buffer). The key is that you still need two passes, but you can keep only O(1) additional state per element.
Q3Why does the presence of multiple zeros in the input array simplify the output, and how does your algorithm handle it?
If there are two or more zeros, every output element will be zero because each product excludes at most one zero. The prefix‑suffix method naturally yields zero for all positions without extra checks, as the zero propagates through the prefix or suffix multiplication.
Examples
Input
[1, 2, 3, 4]
Output
[24,12,8,6]
Explanation: Step-by-step: Given the input [1, 2, 3, 4], we calculate the product of all numbers except the first number 1. The product of remaining elements is 2 * 3 * 4 = 24. Similarly, we calculate the product of all numbers except the second number 2, which is 1 * 3 * 4 = 12. We repeat this process for the third and fourth numbers, giving us the output [24, 12, 8, 24].
Input
[5, 1, 1, 1]
Output
[1,5,5,5]
Explanation: Step-by-step: Given the input [5, 1, 1, 1], we calculate the product of all numbers except the first number 5. The product of remaining elements is 1 * 1 * 1 = 1. Since the product of remaining elements for each element separately is indeed 1, the output is [5, 5, 5, 5].
Constraints
- 2 <= n <= 10^5
- -30 <= arr[i] <= 30
Optimal Approach & Strategy
Compute prefix products in a forward pass and suffix products in a backward pass, multiplying them together for each index. This yields O(n) time and O(1) auxiliary space (excluding the output array).
Brute Force Approach
For each index i, multiply every element except nums[i] by looping through the entire array, resulting in O(n²) time. This repeats the same work many times and quickly becomes too slow for large inputs.
Verified Code Solutions
function productExceptSelf(nums) {
const n = nums.length;
const left = new Array(n).fill(1);
const right = new Array(n).fill(1);
const result = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
left[i] = left[i - 1] * nums[i - 1];
}
for (let i = n - 2; i >= 0; i--) {
right[i] = right[i + 1] * nums[i + 1];
}
for (let i = 0; i < n; i++) {
result[i] = left[i] * right[i];
}
return result;
}#include <vector>
using namespace std;
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> left(n, 1), right(n, 1), result(n, 1);
for (int i = 1; i < n; ++i) {
left[i] = left[i - 1] * nums[i - 1];
}
for (int i = n - 2; i >= 0; --i) {
right[i] = right[i + 1] * nums[i + 1];
}
for (int i = 0; i < n; ++i) {
result[i] = left[i] * right[i];
}
return result;
}
public class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] left = new int[n];
int[] right = new int[n];
int[] result = new int[n];
java.util.Arrays.fill(left, 1);
java.util.Arrays.fill(right, 1);
java.util.Arrays.fill(result, 1);
for (int i = 1; i < n; i++) {
left[i] = left[i - 1] * nums[i - 1];
}
for (int i = n - 2; i >= 0; i--) {
right[i] = right[i + 1] * nums[i + 1];
}
for (int i = 0; i < n; i++) {
result[i] = left[i] * right[i];
}
return result;
}
}
def product_except_self(nums):
n = len(nums)
left = [1] * n
right = [1] * n
result = [1] * n
for i in range(1, n):
left[i] = left[i - 1] * nums[i - 1]
for i in range(n - 2, -1, -1):
right[i] = right[i + 1] * nums[i + 1]
for i in range(n):
result[i] = left[i] * right[i]
return result
function productExceptSelf(nums) {
const n = nums.length;
const left = new Array(n).fill(1);
const right = new Array(n).fill(1);
const result = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
left[i] = left[i - 1] * nums[i - 1];
}
for (let i = n - 2; i >= 0; i--) {
right[i] = right[i + 1] * nums[i + 1];
}
for (let i = 0; i < n; i++) {
result[i] = left[i] * right[i];
}
return result;
}
Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.