Product of Array Except Self

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.

Key insight

• Division would be the obvious answer but it is explicitly forbidden — and breaks when the array contains zeros.
• The key insight: output[i] = (product of everything LEFT of i) × (product of everything RIGHT of i).
• You can compute both sides in separate passes without ever dividing.

Examples

Input	Output
[1,2,3,4]	[24,12,8,6]
[-1,1,0,-3,3]	[0,-9,0,9,0]

Constraints

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

Real-World Applications

Where this pattern appears

• Parallel computation — computing per-node contributions in distributed matrix operations.
• Financial returns — computing total portfolio return excluding each individual asset’s contribution.
• Leave-one-out cross validation — machine learning metric where you exclude each data point’s own contribution.
• Signal processing — computing running products that exclude self-interference.

Complexity Comparison

Approach	Time	Space	Best When
Prefix/Suffix Arrays	O(n)	O(n)	Clarity matters, extra memory allowed
Two-Pass (O(1) space)	O(n)	O(1)*	Follow-up requirement, memory-constrained

*The output array is not counted as extra space per the problem convention.

Approach 1: Prefix/Suffix Arrays

★ Recommended

⏱ Time O(n) Two passes 💾 Space O(n) Two extra arrays

Build a prefix array where prefix[i] is the product of all elements to the left of index i, and a suffix array where suffix[i] is the product of all elements to the right of index i. The answer at each index is simply prefix[i] * suffix[i].

Step-by-step Example

Input: [1, 2, 3, 4]

i	prefix[i]	suffix[i]	output[i]
0	1	24	24
1	1	12	12
2	2	4	8
3	6	1	6

Animated walkthrough

Building prefix and suffix arrays

Use Next or Autoplay to watch the prefix array fill left→right, then the suffix array fill right→left, before combining them.

Back Autoplay Next Reset

Step 1 of 4

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function productExceptSelf(nums):
    n = len(nums)
    prefix = [1] * n
    suffix = [1] * n
    for i in range(1, n):
        prefix[i] = prefix[i-1] * nums[i-1]
    for i in range(n-2, -1, -1):
        suffix[i] = suffix[i+1] * nums[i+1]
    return [prefix[i] * suffix[i] for i in range(n)]

Solution Code

Python

product_except_self_prefix_suffix.py

from typing import List


def product_except_self(nums: List[int]) -> List[int]:
    n = len(nums)
    prefix = [1] * n
    suffix = [1] * n

    for i in range(1, n):
        prefix[i] = prefix[i - 1] * nums[i - 1]

    for i in range(n - 2, -1, -1):
        suffix[i] = suffix[i + 1] * nums[i + 1]

    return [prefix[i] * suffix[i] for i in range(n)]

C++

product_except_self_prefix_suffix.cpp

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix(n, 1);
        vector<int> suffix(n, 1);

        for (int i = 1; i < n; ++i)
            prefix[i] = prefix[i - 1] * nums[i - 1];

        for (int i = n - 2; i >= 0; --i)
            suffix[i] = suffix[i + 1] * nums[i + 1];

        vector<int> output(n);
        for (int i = 0; i < n; ++i)
            output[i] = prefix[i] * suffix[i];

        return output;
    }
};

Java

product_except_self_prefix_suffix.java

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n];
        int[] suffix = new int[n];
        prefix[0] = 1;
        suffix[n - 1] = 1;

        for (int i = 1; i < n; i++)
            prefix[i] = prefix[i - 1] * nums[i - 1];

        for (int i = n - 2; i >= 0; i--)
            suffix[i] = suffix[i + 1] * nums[i + 1];

        int[] output = new int[n];
        for (int i = 0; i < n; i++)
            output[i] = prefix[i] * suffix[i];

        return output;
    }
}

JavaScript

product_except_self_prefix_suffix.js

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function productExceptSelf(nums) {
    const n = nums.length;
    const prefix = new Array(n).fill(1);
    const suffix = new Array(n).fill(1);

    for (let i = 1; i < n; i++)
        prefix[i] = prefix[i - 1] * nums[i - 1];

    for (let i = n - 2; i >= 0; i--)
        suffix[i] = suffix[i + 1] * nums[i + 1];

    return Array.from({ length: n }, (_, i) => prefix[i] * suffix[i]);
}

Rust

product_except_self_prefix_suffix.rs

impl Solution {
    pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut prefix = vec![1i32; n];
        let mut suffix = vec![1i32; n];

        for i in 1..n {
            prefix[i] = prefix[i - 1] * nums[i - 1];
        }

        for i in (0..n - 1).rev() {
            suffix[i] = suffix[i + 1] * nums[i + 1];
        }

        (0..n).map(|i| prefix[i] * suffix[i]).collect()
    }
}

Go

product_except_self_prefix_suffix.go

func productExceptSelf(nums []int) []int {
  n := len(nums)
  prefix := make([]int, n)
  suffix := make([]int, n)
  prefix[0] = 1
  suffix[n-1] = 1

  for i := 1; i < n; i++ {
    prefix[i] = prefix[i-1] * nums[i-1]
  }

  for i := n - 2; i >= 0; i-- {
    suffix[i] = suffix[i+1] * nums[i+1]
  }

  output := make([]int, n)
  for i := 0; i < n; i++ {
    output[i] = prefix[i] * suffix[i]
  }

  return output
}

Approach 2: Two-Pass O(1) Space

💾 Space-Optimal

⏱ Time O(n) 💾 Space O(1) Output array only

Reuse the output array itself instead of allocating separate prefix and suffix arrays. The first pass (left→right) fills each slot with the running prefix product. The second pass (right→left) multiplies each slot by a running suffix product variable.

Step-by-step Example

Input: [1, 2, 3, 4]

After pass 1 (left prefix into output): output = [1, 1, 2, 6]

Pass 2 (right→left, running suffix starts at 1):

i	output[i] before	suffix	output[i] after	suffix update
3	6	1	6×1 = 6	1×4 = 4
2	2	4	2×4 = 8	4×3 = 12
1	1	12	1×12 = 12	12×2 = 24
0	1	24	1×24 = 24	—

Result: [24, 12, 8, 6]

Animated walkthrough

Two-pass in-place product

Pass 1 fills the output with left-prefix products. Pass 2 multiplies in right-suffix products using a single variable.

Back Autoplay Next Reset

Step 1 of 3

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function productExceptSelfOptimal(nums):
    n = len(nums)
    output = [1] * n
    prefix = 1
    for i in range(n):
        output[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n-1, -1, -1):
        output[i] *= suffix
        suffix *= nums[i]
    return output

Solution Code

Python

product_except_self_two_pass.py

from typing import List


def product_except_self(nums: List[int]) -> List[int]:
    n = len(nums)
    output = [1] * n

    prefix = 1
    for i in range(n):
        output[i] = prefix
        prefix *= nums[i]

    suffix = 1
    for i in range(n - 1, -1, -1):
        output[i] *= suffix
        suffix *= nums[i]

    return output

C++

product_except_self_two_pass.cpp

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> output(n, 1);

        int prefix = 1;
        for (int i = 0; i < n; ++i) {
            output[i] = prefix;
            prefix *= nums[i];
        }

        int suffix = 1;
        for (int i = n - 1; i >= 0; --i) {
            output[i] *= suffix;
            suffix *= nums[i];
        }

        return output;
    }
};

Java

product_except_self_two_pass.java

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] output = new int[n];

        int prefix = 1;
        for (int i = 0; i < n; i++) {
            output[i] = prefix;
            prefix *= nums[i];
        }

        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            output[i] *= suffix;
            suffix *= nums[i];
        }

        return output;
    }
}

JavaScript

product_except_self_two_pass.js

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function productExceptSelf(nums) {
    const n = nums.length;
    const output = new Array(n).fill(1);

    let prefix = 1;
    for (let i = 0; i < n; i++) {
        output[i] = prefix;
        prefix *= nums[i];
    }

    let suffix = 1;
    for (let i = n - 1; i >= 0; i--) {
        output[i] *= suffix;
        suffix *= nums[i];
    }

    return output;
}

Rust

product_except_self_two_pass.rs

impl Solution {
    pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut output = vec![1i32; n];

        let mut prefix = 1;
        for i in 0..n {
            output[i] = prefix;
            prefix *= nums[i];
        }

        let mut suffix = 1;
        for i in (0..n).rev() {
            output[i] *= suffix;
            suffix *= nums[i];
        }

        output
    }
}

Go

product_except_self_two_pass.go

func productExceptSelf(nums []int) []int {
  n := len(nums)
  output := make([]int, n)

  prefix := 1
  for i := 0; i < n; i++ {
    output[i] = prefix
    prefix *= nums[i]
  }

  suffix := 1
  for i := n - 1; i >= 0; i-- {
    output[i] *= suffix
    suffix *= nums[i]
  }

  return output
}

Common mistakes

• Forgetting that prefix[0] and suffix[n-1] must both start as 1 (the multiplicative identity).
• Off-by-one: prefix[i] should be the product of nums[0..i-1], not including nums[i].
• Division approach: fails when the array contains zeros (division by zero).

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

product_of_array_except_self_space_optimized.py

"""
Solution for Product of Array Except Self
"""

def solve():
    """Implementation for approach 3 of Product of Array Except Self"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

product_of_array_except_self_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Product of Array Except Self
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

ProductOfArrayExceptSelfSpaceOptimized.java

/**
 * Solution for Product of Array Except Self
 * Approach 3
 */
public class ProductOfArrayExceptSelfSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

product_of_array_except_self_space_optimized.js

/**
 * Solution for Product of Array Except Self
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

product_of_array_except_self_space_optimized.rs

/// Solution for Product of Array Except Self
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

product_of_array_except_self_space_optimized.go

package main

import "fmt"

// Solution for Product of Array Except Self
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Trapping Rain Water ↗ Hard #42
• Subarray Sum Equals K ↗ Medium #560
• Maximum Product Subarray ↗ Medium #152

Interview Tips

Key points to mention

• Always mention the O(1) space follow-up unprompted — it signals awareness of the classic progression.
• The output array is considered O(1) extra space per the problem statement (it is the return value).
• Zero handling: ask “what if the array contains zeros?” — this approach handles it correctly, division would not.

← Previous
#236 Lowest Common Ancestor of a Binary Tree Next
#242 Valid Anagram →