Array Multiplicative Exclusion

You're in an Amazon onsite and the interviewer writes [1, 2, 3, 4] on the whiteboard. "Return an array where each element is the product of every other element. Oh, and you can't use division." That last constraint is what turns a trivial problem into a genuinely interesting one. This is Array Multiplicative Exclusion, known on most platforms as Product of Array Except Self. It gets asked at Adobe, Amazon, Google, Meta, Apple, and a long list of companies, and it tests whether you can decompose a problem into two complementary passes over an array.

TL;DR

Make two passes. In the first pass (left to right), build a prefix product so that answer[i] holds the product of everything to the left of index i. In the second pass (right to left), multiply each answer[i] by a running suffix product that accumulates everything to the right. The result at each index is the product of all elements except itself. O(n) time, O(1) extra space beyond the output array, no division needed.

Prefer a different language? Jump to solutions in other languages.

The Problem

Given an integer array nums, return an array answer such that answer[i] equals the product of all elements in nums except nums[i]. The solution must run in O(n) time and must not use division.

productExceptSelf([1,2,3,4]) => [24,12,8,6]
productExceptSelf([-1,1,0,-3,3]) => [0,0,9,0,0]

Constraints:

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

Why This Problem Matters

This problem shows up constantly in interviews because it tests a few things at once. Can you think beyond brute force? Can you handle the no-division constraint without panicking? Do you understand how prefix computations work? The two-pass prefix-suffix technique that solves this problem also applies to Trapping Rain Water, stock price problems, and various range query tasks. It's a pattern worth internalizing.

The Brute Force Trap

The naive approach is to compute each answer[i] by iterating through the entire array and multiplying every element except nums[i]. That gives you O(n^2) time, which is too slow for arrays up to 10^5 elements.

You might also think: "Just compute the total product, then divide by nums[i] for each position." That works when there are no zeros, but the problem says no division. And even if division were allowed, a single zero in the array would cause a division-by-zero error.

So we need something smarter.

The Two-Pass Approach

Think about what answer[i] actually needs: the product of all elements to the left of i, multiplied by the product of all elements to the right of i.

If you had those two products for every index, you'd be done. And you can compute both with simple linear passes.

Left pass (prefix products): Walk left to right, keeping a running product. Before you process index i, the running product contains nums[0] * nums[1] * ... * nums[i-1]. Store that in answer[i], then multiply the running product by nums[i].

Right pass (suffix products): Walk right to left, keeping another running product. Before you process index i, this product contains nums[i+1] * nums[i+2] * ... * nums[n-1]. Multiply answer[i] by this value, then update the running product.

After both passes, each answer[i] holds the product of every element except nums[i].

Step-by-Step Walkthrough

For input [1, 2, 3, 4]:

Prefix Pass (left to right)

We maintain a prefix variable starting at 1. At each index, we store the current prefix in answer[i], then update prefix by multiplying it with nums[i].

After this pass, answer = [1, 1, 2, 6]. Each position holds the product of everything to its left.

Suffix Pass (right to left)

Now we walk backward with a suffix variable starting at 1. At each index, we multiply answer[i] by the current suffix, then update suffix by multiplying it with nums[i].

The Complete Picture

The final output is [24, 12, 8, 6]. You can verify: 24 = 2*3*4, 12 = 1*3*4, 8 = 1*2*4, 6 = 1*2*3.

Implementation

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

    // Left pass: build prefix products
    answer[0] = 1;
    for (int i = 1; i < n; i++) {
      answer[i] = answer[i - 1] * nums[i - 1];
    }

    // Right pass: multiply by suffix products
    int suffixProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
      answer[i] *= suffixProduct;
      suffixProduct *= nums[i];
    }

    return answer;
  }
}

The prefix pass stores answer[i] = answer[i-1] * nums[i-1], which means answer[i] is the product of nums[0] through nums[i-1]. The suffix pass multiplies each answer[i] by the product of nums[i+1] through nums[n-1], completing the result.

One thing to notice: the prefix pass here stores prefix products directly into the answer array rather than using a separate variable. Both approaches are equivalent, and the solution code on Firecode uses the separate-variable style. The end result is the same.

Handling Zeros

Zeros deserve a closer look because they affect how products propagate. For [-1, 1, 0, -3, 3]:

Prefix pass with a zero

Once the prefix hits the zero at index 2, every subsequent prefix product is zero.

Suffix pass with a zero

The suffix product picks up the zero at index 2 on its way left, making suffix zero for indices 1 and 0. The only index that avoids zero contamination from both sides is index 2 itself, which gets (-1) * 1 * (-3) * 3 = 9.

Final output: [0, 0, 9, 0, 0]. When an array has exactly one zero, only the zero's position gets a nonzero result. If there are two or more zeros, every position is zero.

Complexity Analysis

Time: O(n)

Two passes over the array, each doing O(1) work per element. Total: 2n operations, which simplifies to O(n).

Space: O(n)

The output array uses O(n) space. If the problem considers the output array "free" (as many interview problems do), then the extra space is O(1) since we only use a single running variable in each pass.

Common Mistakes

1. Reaching for division first. The constraint exists to push you toward the prefix-suffix approach. Division also fails with zeros.

2. Forgetting the initial value. Both the prefix and suffix running products must start at 1, not 0. Multiplying by 0 would zero out everything.

3. Off-by-one in the prefix pass. answer[i] should equal the product of elements before index i, not including nums[i]. Make sure you store the prefix before multiplying by nums[i], not after.

4. Updating suffix before multiplying. In the right pass, multiply answer[i] by the suffix first, then update the suffix with nums[i]. Reversing this order would include nums[i] in its own product.

Interview Tips

When you encounter this problem:

1. Start by explaining why division won't work. This shows the interviewer you understand the constraint and aren't just memorizing a trick.

2. Draw the prefix and suffix arrays. For [1, 2, 3, 4], write out prefix = [1, 1, 2, 6] and suffix = [24, 12, 4, 1] and show that multiplying them elementwise gives the answer. This makes the approach concrete before you write code.

3. Point out the space optimization. Mention that you can avoid a second array by computing the suffix product in-place during the backward pass.

4. Discuss the zero edge case. Interviewers often follow up with "What if there's a zero?" Your two-pass approach handles it automatically, but being able to explain why shows deep understanding.

Key Takeaways

• The no-division constraint forces a decomposition into prefix and suffix products, which is the core technique behind this problem.
• Two linear passes (one forward, one backward) combine to give each index the product of every other element in O(n) time.
• The suffix pass reuses the prefix array, keeping auxiliary space at O(1) beyond the output.
• Zeros propagate through products naturally: one zero leaves a single nonzero output, two or more zeros produce all zeros.
• This prefix-suffix pattern transfers directly to problems like Trapping Rain Water (prefix-max and suffix-max) and range product queries.

Solutions in Other Languages

Python

class Solution:
    def product_except_self(self, nums):
        length = len(nums)
        answer = [0] * length

        prefix = 1
        for i in range(length):
            answer[i] = prefix
            prefix *= nums[i]

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

        return answer

JavaScript

productExceptSelf(nums) {
  const n = nums.length;
  const answer = new Array(n).fill(1);

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

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

  return answer;
}

TypeScript

productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const answer: number[] = new Array(n).fill(1);

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

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

  return answer;
}

C++

std::vector<int> productExceptSelf(std::vector<int> &nums) {
  int n = nums.size();
  std::vector<int> answer(n, 1);

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

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

  return answer;
}

Go

func (s *Solution) ProductExceptSelf(nums []int) []int {
  length := len(nums)
  answer := make([]int, length)

  for i := range answer {
    answer[i] = 1
  }

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

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

  return answer
}

Scala

def productExceptSelf(nums: Array[Int]): Array[Int] = {
  val n = nums.length
  val answer = Array.fill(n)(1)

  var prefix = 1
  for (i <- nums.indices) {
    answer(i) = prefix
    prefix *= nums(i)
  }

  var suffix = 1
  for (i <- nums.indices.reverse) {
    answer(i) *= suffix
    suffix *= nums(i)
  }

  answer
}

Kotlin

fun productExceptSelf(nums: IntArray): IntArray {
  val n = nums.size
  val answer = IntArray(n)

  answer[0] = 1
  for (i in 1 until n) {
    answer[i] = answer[i - 1] * nums[i - 1]
  }

  var suffixProduct = 1
  for (i in n - 1 downTo 0) {
    answer[i] *= suffixProduct
    suffixProduct *= nums[i]
  }

  return answer
}

Ruby

def product_except_self(nums)
  n = nums.length
  answer = Array.new(n, 0)

  answer[0] = 1
  (1...n).each do |i|
    answer[i] = answer[i - 1] * nums[i - 1]
  end

  suffix_product = 1
  (n - 1).downto(0) do |i|
    answer[i] *= suffix_product
    suffix_product *= nums[i]
  end

  answer
end

Rust

pub fn product_except_self(&self, nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    let mut answer = vec![1; n];

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

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

    answer
}

Swift

func productExceptSelf(_ nums: [Int]) -> [Int] {
    let n = nums.count
    var answer = [Int](repeating: 1, count: n)

    var prefix = 1
    for i in 0..<n {
        answer[i] = prefix
        prefix *= nums[i]
    }

    var suffix = 1
    for i in stride(from: n - 1, through: 0, by: -1) {
        answer[i] *= suffix
        suffix *= nums[i]
    }

    return answer
}

C#

public int[] productExceptSelf(int[] nums) {
    int n = nums.Length;
    var answer = new int[n];

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

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

    return answer;
}

Dart

List<int> productExceptSelf(List<int> nums) {
  int n = nums.length;
  List<int> answer = List.filled(n, 1);

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

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

  return answer;
}

PHP

public function productExceptSelf(array $nums): array {
    $n = count($nums);
    $answer = array_fill(0, $n, 1);

    for ($i = 1; $i < $n; $i++) {
        $answer[$i] = $answer[$i - 1] * $nums[$i - 1];
    }

    $suffixProduct = 1;
    for ($i = $n - 1; $i >= 0; $i--) {
        $answer[$i] *= $suffixProduct;
        $suffixProduct *= $nums[$i];
    }

    return $answer;
}

Related Problems

Once you're comfortable with the prefix-suffix product pattern, these problems build on the same ideas:

• Trapping Rain Water - uses prefix-max and suffix-max instead of prefix-product
• Maximum Product Subarray - tracks running min and max products through a single pass
• Subarray Product Less Than K - sliding window with multiplicative state
• Range Sum Query - the additive version of prefix computation

This problem and hundreds of others are available on Firecode, where spaced repetition helps you actually retain the patterns you learn. If you found the prefix-suffix decomposition useful here, practicing related problems will solidify the technique so it becomes second nature in your next interview.