12  Product of Array Except Self

Rank 10 · Pattern: prefix and suffix accumulation · Target: \(O(n)\) time, \(O(1)\) auxiliary space

12.1 Problem definition

Given an integer array nums, return an array whose value at each index i is the product of every element of nums except nums[i]. Do not use division.

12.2 Clarifying questions

  1. Are zeros and negative values allowed?
  2. What result should a one-element or empty input produce?
  3. What overflow behavior should I assume?
  4. Does the returned array count toward the auxiliary-space limit?
  5. Can the input array be null, and may it be modified?

12.3 Sample answers

  1. Yes. Zeros and negative values are valid input.
  2. Use the empty-product value 1, so [5] produces [1]; an empty input produces an empty output.
  3. Ordinary signed 32-bit int arithmetic is acceptable; assume all intermediate and returned products fit in that range.
  4. No. The output array is excluded when measuring auxiliary space.
  5. The input is non-null and should not be modified.

12.4 Data structure: output as working storage

Only the result collection is needed. The first pass stores left-side products in it; the second pass multiplies in right-side products. Two scalar accumulators avoid separate prefix and suffix collections.

Allocate an int[] with the input length.

[1] * len(nums) allocates and initializes the result list.

vec![1; nums.len()] allocates and initializes the result vector while the input remains a borrowed slice.

12.5 Approach and invariant

Computing each product independently is \(O(n^2)\). Division is forbidden and would also require special handling for zeros.

First move left to right. Before multiplying by nums[i], prefix equals the product strictly to the left, so assign it to answer[i].

Then move right to left. suffix equals the product strictly to the right; multiply it into the stored prefix.

For [1,2,3,4]:

index left product stored right product applied final
0 1 24 24
1 1 12 12
2 2 4 8
3 6 1 6 
answer[i] = (nums[0] ... nums[i-1]) * (nums[i+1] ... nums[n-1])
             prefix to the left            suffix to the right

Invariant: after the first pass, answer[i] is the product left of i. When the second pass visits i, suffix is the product right of i.

12.6 Minimal solution

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class ProductExceptSelfSolution {
    static int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];
        int prefix = 1;
        for (int i = 0; i < nums.length; i++) {
            answer[i] = prefix;
            prefix *= nums[i];
        }

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

    @Test public void emptyInputProducesEmptyOutput() {
        assertArrayEquals(new int[0], productExceptSelf(new int[0]));
    }

    @Test public void singletonUsesEmptyProduct() {
        assertArrayEquals(new int[] {1}, productExceptSelf(new int[] {5}));
    }

    @Test public void twoValuesUseTheOtherValue() {
        assertArrayEquals(new int[] {3, 2}, productExceptSelf(new int[] {2, 3}));
    }

    @Test public void ordinaryProducts() {
        assertArrayEquals(new int[] {24, 12, 8, 6},
                          productExceptSelf(new int[] {1, 2, 3, 4}));
    }

    @Test public void handlesOneZero() {
        assertArrayEquals(new int[] {0, 0, 8, 0},
                          productExceptSelf(new int[] {1, 2, 0, 4}));
    }

    @Test public void handlesTwoZeros() {
        assertArrayEquals(new int[] {0, 0, 0},
                          productExceptSelf(new int[] {0, 2, 0}));
    }

    @Test public void handlesNegativeValues() {
        assertArrayEquals(new int[] {-6, 3, -2},
                          productExceptSelf(new int[] {-1, 2, -3}));
    }

    @Test public void doesNotModifyInput() {
        int[] input = {1, 2, 3, 4};
        int[] original = input.clone();

        productExceptSelf(input);

        assertArrayEquals(original, input);
    }

    public static void main(String[] args) {
        JUnitCore.main("ProductExceptSelfSolution");
    }
}
import unittest


def product_except_self(nums):
    answer = [1] * len(nums)

    prefix = 1
    for index, value in enumerate(nums):
        answer[index] = prefix
        prefix *= value

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

    return answer


class ProductExceptSelfTests(unittest.TestCase):
    def test_empty_input(self):
        self.assertEqual([], product_except_self([]))

    def test_singleton_uses_empty_product(self):
        self.assertEqual([1], product_except_self([5]))

    def test_ordinary_products(self):
        self.assertEqual([24, 12, 8, 6], product_except_self([1, 2, 3, 4]))

    def test_handles_one_zero(self):
        self.assertEqual([0, 0, 8, 0], product_except_self([1, 2, 0, 4]))

    def test_handles_two_zeros(self):
        self.assertEqual([0, 0, 0], product_except_self([0, 2, 0]))

    def test_handles_negative_values(self):
        self.assertEqual([-6, 3, -2], product_except_self([-1, 2, -3]))

    def test_does_not_modify_input(self):
        nums = [1, 2, 3, 4]
        original = nums.copy()
        product_except_self(nums)
        self.assertEqual(original, nums)


if __name__ == "__main__":
    unittest.main()
pub fn product_except_self(nums: &[i32]) -> Vec<i32> {
    let mut answer = vec![1; nums.len()];

    let mut prefix = 1;
    for (index, &value) in nums.iter().enumerate() {
        answer[index] = prefix;
        prefix *= value;
    }

    let mut suffix = 1;
    for index in (0..nums.len()).rev() {
        answer[index] *= suffix;
        suffix *= nums[index];
    }

    answer
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn empty_input() {
        assert_eq!(Vec::<i32>::new(), product_except_self(&[]));
    }

    #[test]
    fn singleton_uses_empty_product() {
        assert_eq!(vec![1], product_except_self(&[5]));
    }

    #[test]
    fn ordinary_products() {
        assert_eq!(vec![24, 12, 8, 6], product_except_self(&[1, 2, 3, 4]));
    }

    #[test]
    fn handles_one_zero() {
        assert_eq!(vec![0, 0, 8, 0], product_except_self(&[1, 2, 0, 4]));
    }

    #[test]
    fn handles_two_zeros() {
        assert_eq!(vec![0, 0, 0], product_except_self(&[0, 2, 0]));
    }

    #[test]
    fn handles_negative_values() {
        assert_eq!(vec![-6, 3, -2], product_except_self(&[-1, 2, -3]));
    }
}

12.7 High-value tests

Input Expected Purpose
[1,2,3,4] [24,12,8,6] ordinary
[1,2,0,4] [0,0,8,0] one zero
[0,2,0] [0,0,0] two zeros
[-1,2,-3] [-6,3,-2] signs
[5] [1] empty product convention
[] [] empty input contract

12.8 Complexity and correctness

Two linear passes give \(O(n)\) time. Excluding the required output, the method uses two integer accumulators: \(O(1)\) auxiliary space.

Every factor other than nums[i] lies either strictly left or strictly right of i. The two invariants prove those products are computed exactly once and multiplied together, while nums[i] is never included.

12.9 If the interviewer pushes

  • Use long[] and long accumulators if the contract needs a wider range; even long can overflow for unrestricted products.
  • If output space counts, \(O(n)\) is unavoidable simply to return \(n\) answers.
  • Separate prefix and suffix arrays are easier to explain but use \(O(n)\) extra storage.
  • A zero-count/division solution can be linear but violates the stated rule and adds branches; do not lead with it.

12.10 TDD interview script

Confirm that division is forbidden, zeros and negatives are valid, empty products equal 1, input is non-null and must remain unchanged, output space is excluded, and products fit in int. Then write this test list:

  1. Empty input
  2. Singleton
  3. Two values
  4. Ordinary array
  5. Negative values
  6. One zero
  7. Two zeros
  8. Input preservation

Use one red–green–refactor cycle per behavior. Confirm the intended failure, add only the next general pass or state update, rerun the complete example, and refactor while green. Compare returned sequences by value, and test input preservation through a copied snapshot rather than object identity.

From book/src, run:

./java/run.sh ProductExceptSelfSolution
./python/run.sh product_except_self_solution
./rust/run.sh product_except_self_solution

Narrate the decomposition: every answer is a left product times a right product. Store left products directly in the required output, then multiply right products into those slots while scanning backward.

12.10.1 Pseudocode

answer = new array of nums.length
prefix = 1

for i from left to right:
    answer[i] = prefix
    prefix = prefix * nums[i]

suffix = 1
for i from right to left:
    answer[i] = answer[i] * suffix
    suffix = suffix * nums[i]

return answer

After the first pass, answer[i] is the product strictly left of i. When the second pass visits i, suffix is the product strictly right of it.

12.10.2 TDD sequence

Step Test code added Production code added or changed
1. Empty shape emptyInputProducesEmptyOutput Allocate an output with the same length; both passes naturally skip an empty input.
2. Empty product singletonUsesEmptyProduct Initialize both accumulators to 1, producing the multiplicative identity when no other value exists.
3. Both directions twoValuesUseTheOtherValue Add the left-to-right prefix pass and right-to-left suffix pass.
4. General products ordinaryProducts Update each accumulator after using it, so the current element is excluded from its own result.
5. Signed values handlesNegativeValues Triangulate ordinary integer multiplication without sign-specific branches.
6. One zero handlesOneZero Confirm that prefix/suffix multiplication naturally leaves the nonzero product only at the zero’s position.
7. Multiple zeros handlesTwoZeros Confirm that every result becomes zero without division or zero-count special cases.
8. Input ownership doesNotModifyInput Keep all working state in the output and scalar accumulators; never write into nums.

The progression derives the two-pass invariant from the smallest arrays. Zero tests demonstrate why the division-free design is robust without adding conditional logic.