3.20 Product of Array Except Self

3.20.1 Problem Metadata

3.20.2 Description

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.

3.20.3 Examples

Example 1:

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:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Explanation:
- answer[0] = 1 × 0 × (-3) × 3 = 0
- answer[1] = (-1) × 0 × (-3) × 3 = 0
- answer[2] = (-1) × 1 × (-3) × 3 = 9
- answer[3] = (-1) × 1 × 0 × 3 = 0
- answer[4] = (-1) × 1 × 0 × (-3) = 0

3.20.4 Constraints

  • \(2 \le \text{nums.length} \le 10^5\)
  • \(-30 \le \text{nums}[i] \le 30\)
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer

3.20.5 Follow-up

Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

3.20.6 Solution - Prefix and Suffix Arrays

3.20.6.1 Walkthrough

This solution uses the prefix-suffix product pattern to compute the product of all elements except self without using division.

Core Strategy:

The key insight is that for any element at index i, the product of all other elements equals:

result[i] = (product of all elements before i) × (product of all elements after i)

We can precompute these products using two auxiliary arrays: - Prefix array: prefix[i] stores the product of all elements before index i - Suffix array: suffix[i] stores the product of all elements after index i

Step-by-step execution for nums = [1, 2, 3, 4]:

  1. Build prefix array (left to right):

    prefix[0] = 1              (no elements before index 0)
prefix[1] = 1              (product of nums[0] = 1)
prefix[2] = 1 × 2 = 2      (product of nums[0..1])
prefix[3] = 1 × 2 × 3 = 6  (product of nums[0..2])
→ prefix = [1, 1, 2, 6]

  2. Build suffix array (right to left):

    suffix[3] = 1              (no elements after index 3)
suffix[2] = 4              (product of nums[3] = 4)
suffix[1] = 3 × 4 = 12     (product of nums[2..3])
suffix[0] = 2 × 3 × 4 = 24 (product of nums[1..3])
→ suffix = [24, 12, 4, 1]

  3. Compute result:

    result[0] = prefix[0] × suffix[0] = 1 × 24 = 24
result[1] = prefix[1] × suffix[1] = 1 × 12 = 12
result[2] = prefix[2] × suffix[2] = 2 × 4 = 8
result[3] = prefix[3] × suffix[3] = 6 × 1 = 6
→ result = [24, 12, 8, 6]

Why This Works:

For nums = [a, b, c, d] and index i = 1: - prefix[1] contains product of elements before index 1: a - suffix[1] contains product of elements after index 1: c × d - result[1] = a × (c × d) which is the product except b ✓

This avoids division entirely while maintaining O(n) time complexity.

3.20.6.2 Analysis

  • Time Complexity: O(n)
    • First loop builds prefix array: O(n)
    • Second loop builds suffix array: O(n)
    • Third loop computes result: O(n)
    • Total: O(n + n + n) = O(n)
  • Space Complexity: O(n)
    • Prefix array: O(n)
    • Suffix array: O(n)
    • Result array: O(n) (doesn’t count per problem statement)
    • Total auxiliary space: O(n)

3.20.6.3 Implementation Steps

  1. Initialize three arrays of length n:
    • result to store final output
    • prefix to store product of elements before each index
    • suffix to store product of elements after each index
  2. Build prefix array (left to right):
    • For index 0: prefix[0] = 1 (no elements before)
    • For indices 1 to n-1: prefix[i] = prefix[i-1] × nums[i-1]
  3. Build suffix array (right to left):
    • For index n-1: suffix[n-1] = 1 (no elements after)
    • For indices n-2 down to 0: suffix[i] = suffix[i+1] × nums[i+1]
  4. Compute result:
    • For each index i: result[i] = prefix[i] × suffix[i]
  5. Return result

3.20.6.4 Code - Java

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] result = new int[len];
        //[1, 1, 1*2, 1*2*3]
        int[] prefix = new int[len];
        //[2*3*4, 3*4, 4, 1]
        int[] suffix = new int[len];

        for(int i = 0; i < len; i++) {
            if(i == 0) {
                prefix[i] = 1;
            } else {
                prefix[i] = prefix[i-1] * nums[i-1];
            }
        }

        for(int i = len - 1; i >= 0; i--) {
            if(i == len - 1) {
                suffix[i] = 1;
            } else {
                suffix[i] = suffix[i+1] * nums[i+1];
            }
        }

        for(int i = 0; i < len; i++) {
            result[i] = prefix[i] * suffix[i];
        }

        return result;
    }
}

3.20.7 Solution - Space-Optimized (Follow-up)

3.20.7.1 Walkthrough

This solution achieves O(1) extra space by building the prefix and suffix products directly into the result array, eliminating the need for separate prefix/suffix arrays.

Core Strategy:

  1. First pass (left to right): Build prefix products in result array
  2. Second pass (right to left): Multiply by suffix products using a running variable

Step-by-step execution for nums = [1, 2, 3, 4]:

Pass 1 - Build prefix products:

i=0: result[0] = 1              (no elements before)
i=1: result[1] = 1              (product before: 1)
i=2: result[2] = 1 × 2 = 2      (product before: 1×2)
i=3: result[3] = 1 × 2 × 3 = 6  (product before: 1×2×3)
→ result = [1, 1, 2, 6]

Pass 2 - Multiply by suffix products:

suffix = 1 (start)
i=3: result[3] *= suffix → 6 × 1 = 6;    suffix = 1 × 4 = 4
i=2: result[2] *= suffix → 2 × 4 = 8;    suffix = 4 × 3 = 12
i=1: result[1] *= suffix → 1 × 12 = 12;  suffix = 12 × 2 = 24
i=0: result[0] *= suffix → 1 × 24 = 24;  suffix = 24 × 1 = 24
→ result = [24, 12, 8, 6]

Key Insight: The suffix variable accumulates the product of elements from right to left, eliminating the need for a separate suffix array.

3.20.7.2 Analysis

  • Time Complexity: O(n)
    • First pass: O(n)
    • Second pass: O(n)
    • Total: O(n)
  • Space Complexity: O(1)
    • Only uses one extra variable (suffix)
    • Result array doesn’t count as extra space per problem statement
    • This satisfies the follow-up requirement!

3.20.7.3 Implementation Steps

  1. Initialize result array of length n

  2. First pass (left to right) - Build prefix products:

    • result[0] = 1 (no elements before index 0)
    • For i from 1 to n-1: result[i] = result[i-1] × nums[i-1]

  3. Second pass (right to left) - Multiply by suffix products:

    • Initialize suffix = 1 (running product from right)
    • For i from n-1 down to 0:
      • Multiply current result by suffix: result[i] *= suffix
      • Update suffix: suffix *= nums[i]

  4. Return result

3.20.7.4 Code - Java

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

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

        // Second pass: multiply by suffix products
        int suffix = 1;
        for(int i = len - 1; i >= 0; i--) {
            result[i] *= suffix;
            suffix *= nums[i];
        }

        return result;
    }
}