Log inSign up
mediumLeetCodeNot Started

Product of Array Except Self

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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 · Standard Array Without Zeros:

Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Explanation: - answer[0] = 2 * 3 * 4 = 24 - answer[1] = 1 * 3 * 4 = 12 - answer[2] = 1 * 2 * 4 = 8 - answer[3] = 1 * 2 * 3 = 6

Example 2 · Array with a Single Zero:

Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
Explanation: For index 2 (value 0), the product of other elements is (-1) * 1 * (-3) * 3 = 9. For all other indices, the product includes the 0, making their result 0.

Example 3 · Array with Multiple Zeros:

Input: nums = [0, 4, 0]
Output: [0, 0, 0]
Explanation: Every index excludes one zero, but still contains the other zero, yielding all 0s.

Constraints:

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • The product of any prefix or suffix fits in a 32-bit integer.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Prefix sum / prefix product fundamentals
  • Forward and backward linear array traversals
  • Space optimization using the output buffer

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Overcome mathematical division restrictions using decomposed prefix and suffix arrays.
  • Optimize space from O(N) auxiliary down to O(1) by reusing the output buffer.
  • Safely handle single and multiple zero cases naturally without special conditional branches.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Need cumulative aggregate of all elements except the current index.
  • Division operator / is strictly forbidden.
  • Array may contain zeros.

Algorithmic Decision Tree:

  • When computing aggregated exclude-self metrics without division: Split the calculation into independent prefix and suffix passes.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Nested Loops All Pairs

Intuition

For each element i, compute the product of all elements j != i using a nested loop.

Algorithm

  1. 1. Initialize an answer array result of size n.
  2. 2. For each index i from 0 to n-1: - Set prod = 1. - For each index j from 0 to n-1: - If j != i, prod *= nums[j]. - Set result[i] = prod.
  3. 3. Return result.

Brute Force Nested Loop Product Calculation

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4]
Current operationSTEP 1 OF 6
Calculate res[0]: Exclude index 0
Visual state
Values and pointers at this exact step
table
S
1
2
3
4
0
↑ i=0 (Exclude)
1
2
3
Fixed Idx0
Excluded Val1
Product24
res[24, _, _, _]
Variables at this step
Fixed Idx
0
Excluded Val
1
Product
24
res
[24, _, _, _]
Check / comparison
Product of elements at j in {1, 2, 3}: 2 * 3 * 4 = 24.
Decision / next transition
res[0] = 24. Advance i to index 1.
Why this step matters

Calculate res[0]: Exclude index 0. Multiply all remaining elements: 2 * 3 * 4 = 24. Store res[0] = 24.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<int> productExceptSelf(vector<int>& nums) {
17 int n = nums.size();
18 vector<int> ans(n, 1);
19 for (int i = 0; i < n; ++i) {
20 long long prod = 1;
21 for (int j = 0; j < n; ++j) {
22 if (i != j) prod *= nums[j];
23 }
24 ans[i] = prod;
25 }
26 return ans;
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<int> nums = {1, 2, 3, 4};
33 vector<int> res = sol.productExceptSelf(nums);
34 cout << "Product Except Self: ";
35 for (int x : res) cout << x << " ";
36 cout << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N^2) — For each of the N elements, the inner loop iterates over N-1 elements. Total operations = N * (N-1) = O(N2).
  • Space complexity: O(1) — The output array does not count toward auxiliary space, requiring O(1) extra space.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Prefix and Suffix Product Arrays

Intuition

Precompute two arrays: prefix[i] storing product of elements before i, and suffix[i] storing product of elements after i.

Algorithm

  1. 1. Allocate prefix array of size n with prefix[0] = 1. Fill prefix[i] = prefix[i-1] * nums[i-1].
  2. 2. Allocate suffix array of size n with suffix[n-1] = 1. Fill suffix[i] = suffix[i+1] * nums[i+1].
  3. 3. For each index i, ans[i] = prefix[i] * suffix[i].
  4. 4. Total runtime is O(N) with O(N) auxiliary space.

Separate Prefix & Suffix Auxiliary Arrays Trace

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [1, 2, 3, 4]
Current operationSTEP 1 OF 7
Pass 1 — Precompute Prefix: prefix[0]=1, prefix[1]=1, prefix[2]=12=2, prefix[3]=23=6
Visual state
Values and pointers at this exact step
table
S
1
1
2
6
0
↑ Prefix Array
1
2
3
Prefix[1, 1, 2, 6]
TimeO(N)
Variables at this step
Prefix
[1, 1, 2, 6]
Time
O(N)
Check / comparison
prefix[i] = prefix[i-1] * nums[i-1]. prefix = [1, 1, 2, 6].
Decision / next transition
Stores cumulative product of all elements to the left.
Why this step matters

Pass 1 — Precompute Prefix: prefix[0]=1, prefix[1]=1, prefix[2]=1*2=2, prefix[3]=2*3=6.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<int> productExceptSelf(vector<int>& nums) {
17 int n = nums.size();
18 vector<int> prefix(n, 1), suffix(n, 1), ans(n);
19 for (int i = 1; i < n; ++i) prefix[i] = prefix[i - 1] * nums[i - 1];
20 for (int i = n - 2; i >= 0; --i) suffix[i] = suffix[i + 1] * nums[i + 1];
21 for (int i = 0; i < n; ++i) ans[i] = prefix[i] * suffix[i];
22 return ans;
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<int> nums = {1, 2, 3, 4};
29 vector<int> res = sol.productExceptSelf(nums);
30 cout << "Product Except Self: ";
31 for (int x : res) cout << x << " ";
32 cout << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N) — Building prefix takes O(N), building suffix takes O(N), and combining takes O(N). Total time is O(3N) = O(N).
  • Space complexity: O(N) — Requires two auxiliary arrays of size N for prefix and suffix products.

3. Single Output Array with Running Suffix (O(1) Extra Space)

Intuition

Store prefix products directly in the output array, then traverse backwards using a single scalar variable for suffix products.

Algorithm

  1. 1. Initialize output array ans of size n with ans[0] = 1.
  2. 2. Left pass: For i from 1 to n-1: ans[i] = ans[i-1] * nums[i-1].
  3. 3. Right pass: Initialize suffix = 1. For i from n-1 down to 0: - ans[i] = ans[i] * suffix - suffix = suffix * nums[i].
  4. 4. Return ans. Auxiliary memory is O(1) since output array does not count toward space complexity.

In-Place Output Array with Running Suffix Accumulator Trace

2 of 2 questions left today
Step 1 / 9
Trace timeline11% explored
InputINPUT nums = [1, 2, 3, 4]
Current operationSTEP 1 OF 9
Prefix step 1 — Initialize index 0: The product of an empty prefix is 1, so set res[0] = 1
Visual state
Values and pointers at this exact step
table
res (prefix products)
1
—
—
—
0
↑ i=0
1
2
3
i0
res (Prefixes)[1, —, —, —]
Prefix Product1
Variables at this step
i
0
res (Prefixes)
[1, —, —, —]
Prefix Product
1
Check / comparison
Initialize res[0] = 1 because there are no elements to the left of index 0.
Decision / next transition
Set the first prefix product to 1. Continue to index 1.
Why this step matters

Prefix step 1 — Initialize index 0: The product of an empty prefix is 1, so set res[0] = 1.

Step 1 / 9
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<int> productExceptSelf(vector<int>& nums) {
17 int n = nums.size();
18 vector<int> ans(n, 1);
19 for (int i = 1; i < n; ++i) {
20 ans[i] = ans[i - 1] * nums[i - 1];
21 }
22 int suffix = 1;
23 for (int i = n - 1; i >= 0; --i) {
24 ans[i] *= suffix;
25 suffix *= nums[i];
26 }
27 return ans;
28 }
29};
30
31int main() {
32 Solution sol;
33 vector<int> nums = {1, 2, 3, 4};
34 vector<int> res = sol.productExceptSelf(nums);
35 cout << "Product Except Self: ";
36 for (int x : res) cout << x << " ";
37 cout << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N) — Two linear passes through the array. Total operations are O(2N) = O(N).
  • Space complexity: O(1) — Only uses a single integer variable for running suffix product. Auxiliary memory is strictly O(1).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Nested Loops All PairsO(N^2)O(1)For each element i, compute the product of all elements j != i using a nested loop.Repeated redundant scans over the input.
2.Approach 2: Prefix and Suffix Product ArraysO(N)O(N)Precompute two arrays: prefix[i] storing product of elements before i, and suffix[i] storing product of elements after i.Auxiliary memory allocation or sorting step.
3.Approach 3: Single Output Array with Running Suffix (O(1) Extra Space)OptimalO(N)O(1)Store prefix products directly in the output array, then traverse backwards using a single scalar variable for suffix products.None. Asymptotically optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • One Zero in Array [-1, 1, 0, -3, 3] — Input: `, Expected: ` —
  • Multiple Zeros [0, 4, 0] — Input: `, Expected: ` —
  • Array with Negative Numbers — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Product of Array Except Self?

2.Why is the brute force approach suboptimal for large inputs in Product of Array Except Self?

3.Which data structure or technique enables the optimal solution for Product of Array Except Self?

Back to DSA Sheet