Product of Array Except Self

Product of Array Except Self #

Problem Statement #

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Constraint: It’s guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32-bit integer.

Note: Please solve it without division and in O(n) time complexity.

Example #

Input: [1,2,3,4]
Output: [24,12,8,6]

Explanation:

  • Index 0: 2 × 3 × 4 = 24
  • Index 1: 1 × 3 × 4 = 12
  • Index 2: 1 × 2 × 4 = 8
  • Index 3: 1 × 2 × 3 = 6

Initial Intuition (The Forbidden Approach) #

If we were allowed to use division, this problem would be straightforward:

  1. Calculate the product of all numbers in the array
  2. For each index i, divide the total product by nums[i]

This would give us an O(n) solution with minimal space complexity. However, the constraint explicitly forbids division, forcing us to think more creatively.

The Core Insight #

The key observation is understanding what we’re computing at each position. For any index i, we need:

result[i] = nums[0] × nums[1] × ... × nums[i-1] × nums[i+1] × ... × nums[n-1]

Notice this can be split into two parts:

  • Left product: All elements before index i
  • Right product: All elements after index i

So: result[i] = leftProduct[i] × rightProduct[i]

This insight leads us to a solution that avoids repeated calculations by preprocessing the left and right products.

Solution Approach #

Step 1: Calculate Prefix Products #

Create an array where each element contains the product of all elements before it (not including itself).

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

  • Index 0: 1 (no elements before)
  • Index 1: 1 (only 1 before)
  • Index 2: 1 × 2 = 2
  • Index 3: 1 × 2 × 3 = 6

Prefix array: [1, 1, 2, 6]

let pre = [];
for (let i = 0; i < nums.length; i++) {
    pre[i] = (pre[i-1] === undefined ? 1 : pre[i-1]) * nums[i];
}

What this creates: pre[i] contains the product of nums[0] through nums[i] (inclusive).

Step 2: Calculate Suffix Products #

Create an array where each element contains the product of all elements after it (not including itself).

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

  • Index 3: 1 (no elements after)
  • Index 2: 4
  • Index 1: 3 × 4 = 12
  • Index 0: 2 × 3 × 4 = 24

Suffix array: [24, 12, 4, 1]

let post = [];
for (let i = nums.length - 1; i >= 0; i--) {
    post[i] = (post[i+1] === undefined ? 1 : post[i+1]) * nums[i];
}

What this creates: post[i] contains the product of nums[i] through nums[n-1] (inclusive).

Step 3: Combine Results #

Now we have:

  • pre[i-1]: Product of all elements before index i
  • post[i+1]: Product of all elements after index i

Multiply these together to get the product excluding nums[i]:

let result = [];
for (let i = 0; i < nums.length; i++) {
    result[i] = (pre[i-1] === undefined ? 1 : pre[i-1]) * 
                (post[i+1] === undefined ? 1 : post[i+1]);
}

Visual Walkthrough #

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

Index:     0    1    2    3
nums:      1    2    3    4

pre:       1    2    6   24   (cumulative product left-to-right)
post:     24   12    4    1   (cumulative product right-to-left)

For each index i, we need:
  result[i] = pre[i-1] × post[i+1]

Index 0: pre[-1] × post[1] = 1 × 12 = 12... wait, that's wrong!

Let me recalculate:
Index 0: (1) × post[1] = 1 × 12 = 12...

Actually, let me trace through more carefully with the actual values:

nums = [1, 2, 3, 4]

After pre loop:
pre[0] = 1 * 1 = 1
pre[1] = 1 * 2 = 2
pre[2] = 2 * 3 = 6
pre[3] = 6 * 4 = 24
pre = [1, 2, 6, 24]

After post loop:
post[3] = 1 * 4 = 4
post[2] = 4 * 3 = 12
post[1] = 12 * 2 = 24
post[0] = 24 * 1 = 24
post = [24, 24, 12, 4]

For result:
result[0] = (undefined → 1) * post[1] = 1 * 24 = 24 ✓
result[1] = pre[0] * post[2] = 1 * 12 = 12 ✓
result[2] = pre[1] * post[3] = 2 * 4 = 8 ✓
result[3] = pre[2] * (undefined → 1) = 6 * 1 = 6 ✓
result = [24, 12, 8, 6]

Complete Solution #

var productExceptSelf = function(nums) {
    // Create array of cumulative products from left to right
    let pre = [];
    for (let i = 0; i < nums.length; i++) {
        pre[i] = (pre[i-1] === undefined ? 1 : pre[i-1]) * nums[i];
    }
    
    // Create array of cumulative products from right to left
    let post = [];
    for (let i = nums.length - 1; i >= 0; i--) {
        post[i] = (post[i+1] === undefined ? 1 : post[i+1]) * nums[i];
    }

    // Combine left and right products
    let result = [];
    for (let i = 0; i < nums.length; i++) {
        result[i] = (pre[i-1] === undefined ? 1 : pre[i-1]) * 
                    (post[i+1] === undefined ? 1 : post[i+1]);
    }

    return result;    
};

Complexity Analysis #

Time Complexity: O(n) #

  • First loop: O(n) to build prefix product array
  • Second loop: O(n) to build suffix product array
  • Third loop: O(n) to combine results
  • Total: O(3n) = O(n)

Space Complexity: O(n) #

  • pre array: O(n)
  • post array: O(n)
  • result array: O(n) (required for output)
  • Total auxiliary space (not counting output): O(2n) = O(n)

Why the Undefined Checks? #

The conditional (pre[i-1] === undefined ? 1 : pre[i-1]) handles edge cases:

  • At index 0: There’s no element before it (pre[-1] is undefined), so we use 1 (multiplicative identity)
  • At index n-1: There’s no element after it (post[n] is undefined), so we use 1

Using 1 as the default ensures these boundary cases don’t affect the multiplication.

Alternative Approaches #

Space-Optimized Solution (O(1) Extra Space) #

We can reduce space complexity by building the result array in-place:

var productExceptSelf = function(nums) {
    const n = nums.length;
    const result = new Array(n);
    
    // Build prefix products directly into result
    result[0] = 1;
    for (let i = 1; i < n; i++) {
        result[i] = result[i-1] * nums[i-1];
    }
    
    // Build suffix products and multiply with prefix
    let rightProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    
    return result;
};

This achieves O(1) extra space (not counting the output array) while maintaining O(n) time complexity.

Key Takeaways #

  1. Pattern Recognition: Breaking the problem into prefix and suffix products is the key insight
  2. Avoid Redundancy: Pre-computing products eliminates repeated calculations
  3. Edge Cases: Handle boundaries carefully with appropriate default values
  4. Space-Time Tradeoffs: Multiple solutions exist with different space complexities
  5. Constraints Matter: The “no division” constraint forces creative problem-solving

Common Pitfalls #

  • Off-by-one errors: Be careful with i-1 and i+1 indices
  • Forgetting edge cases: Always handle the first and last elements specially
  • Integer overflow: The problem guarantees no overflow, but be aware in similar problems
  • Modifying input: Some variations ask for in-place modification; read requirements carefully

Practice Tips #

To master this problem:

  1. Draw out the arrays visually for small examples
  2. Trace through each loop iteration manually
  3. Understand why we need both forward and backward passes
  4. Practice the space-optimized version
  5. Consider what changes if division were allowed

This problem teaches fundamental techniques applicable to many array manipulation challenges, particularly those involving cumulative operations and the prefix-suffix pattern.

Previous Missing Number Top K Frequent Elements Next