13. Product of Array Except Self

🔗 LeetCode Problem: 238. Product of Array Except Self
📊 Difficulty: Medium
🏷️ Topics: Array, Prefix Sum

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.

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

Constraints: - 2 <= nums.length <= 10^5 - -30 <= nums[i] <= 30 - The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer

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.)

---

🎨 Visual Understanding

The Problem Visualized

Input: nums = [1, 2, 3, 4]

For each position, multiply everything EXCEPT that element:

Index 0: answer[0] = 2 * 3 * 4 = 24
         Skip ↓
         [1, 2, 3, 4]

Index 1: answer[1] = 1 * 3 * 4 = 12
            Skip ↓
         [1, 2, 3, 4]

Index 2: answer[2] = 1 * 2 * 4 = 8
               Skip ↓
         [1, 2, 3, 4]

Index 3: answer[3] = 1 * 2 * 3 = 6
                  Skip ↓
         [1, 2, 3, 4]

Output: [24, 12, 8, 6]

Breaking Down Each Product

For nums = [1, 2, 3, 4]

answer[i] = (product of elements LEFT of i) × (product of elements RIGHT of i)

Index 0:
  Left:  nothing → 1
  Right: 2×3×4 = 24
  Result: 1 × 24 = 24

Index 1:
  Left:  1 = 1
  Right: 3×4 = 12
  Result: 1 × 12 = 12

Index 2:
  Left:  1×2 = 2
  Right: 4 = 4
  Result: 2 × 4 = 8

Index 3:
  Left:  1×2×3 = 6
  Right: nothing → 1
  Result: 6 × 1 = 6

Key Insight: Left × Right Product

nums =    [1,    2,    3,    4]
           ↓     ↓     ↓     ↓
Left:     [1,    1,    2,    6]    (cumulative product from left)
Right:    [24,   12,   4,    1]    (cumulative product from right)
           ↓     ↓     ↓     ↓
Answer:   [24,   12,   8,    6]    (left[i] × right[i])

Pattern: answer[i] = leftProduct[i] × rightProduct[i]

---

🎯 Approach 1: Brute Force (Nested Loops)

The Most Natural Thinking 💭

Core Logic:

For each index i:
  Calculate product of all elements except nums[i]
  Multiply all elements before i
  Multiply all elements after i

Two nested loops:
- Outer loop: iterate through each index
- Inner loop: multiply all other elements

Why This Works: - Direct implementation of problem statement - For each position, explicitly calculate product - Easy to understand

Why This is Slow: - Nested loops → O(n²) time - For each element, scan entire array - Not acceptable for large inputs

Implementation

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

    for (int i = 0; i < n; i++) {
        int product = 1;

        // Multiply all elements except nums[i]
        for (int j = 0; j < n; j++) {
            if (j != i) {
                product *= nums[j];
            }
        }

        answer[i] = product;
    }

    return answer;
}

⏰ Time: O(n²) - nested loops
💾 Space: O(1) - excluding output array

---

🎯 Approach 2: Division Trick (Not Allowed)

Thought Process 💭

Core Logic:

Calculate total product of all elements
Then for each position: answer[i] = totalProduct / nums[i]

Example: nums = [1, 2, 3, 4]
  totalProduct = 1 × 2 × 3 × 4 = 24
  answer[0] = 24 / 1 = 24
  answer[1] = 24 / 2 = 12
  answer[2] = 24 / 3 = 8
  answer[3] = 24 / 4 = 6

Why This Works (in theory): - Single pass to calculate total product - Single pass to divide and fill answer - O(n) time complexity

Why This is NOT Valid: - Problem explicitly states: "without using the division operation" - Fails when array contains 0 - Not the solution we're looking for

Edge Case with Zero:

nums = [1, 0, 3]
totalProduct = 0
answer[0] = 0 / 1 = 0
answer[1] = 0 / 0 = undefined! ✗
answer[2] = 0 / 3 = 0

---

✅ Approach 3: Left and Right Product Arrays

The Breakthrough Insight 💡

Core Logic:

Key Observation:
answer[i] = (product of all elements to LEFT of i) × 
            (product of all elements to RIGHT of i)

Strategy:
1. Create leftProduct array
   leftProduct[i] = product of all elements left of index i

2. Create rightProduct array
   rightProduct[i] = product of all elements right of index i

3. Multiply: answer[i] = leftProduct[i] × rightProduct[i]

Building Left Product Array:

nums =        [1,    2,    3,    4]

leftProduct[0] = 1 (no elements to left)
leftProduct[1] = 1 (product of elements before index 1)
leftProduct[2] = 1 × 2 = 2
leftProduct[3] = 1 × 2 × 3 = 6

leftProduct = [1,    1,    2,    6]

Building Right Product Array:

nums =         [1,    2,    3,    4]

rightProduct[3] = 1 (no elements to right)
rightProduct[2] = 4
rightProduct[1] = 3 × 4 = 12
rightProduct[0] = 2 × 3 × 4 = 24

rightProduct = [24,   12,   4,    1]

Final Multiplication:

leftProduct =  [1,    1,    2,    6]
rightProduct = [24,   12,   4,    1]
                ×     ×     ×     ×
answer =       [24,   12,   8,    6]

Why This is Better: - O(n) time - three passes - No division needed - Handles zeros naturally - Clear and understandable

Implementation

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;

    // Create left and right product arrays
    int[] leftProduct = new int[n];
    int[] rightProduct = new int[n];
    int[] answer = new int[n];

    // Build left product array
    leftProduct[0] = 1;  // No elements to left of index 0
    for (int i = 1; i < n; i++) {
        leftProduct[i] = leftProduct[i - 1] * nums[i - 1];
    }

    // Build right product array
    rightProduct[n - 1] = 1;  // No elements to right of last index
    for (int i = n - 2; i >= 0; i--) {
        rightProduct[i] = rightProduct[i + 1] * nums[i + 1];
    }

    // Multiply left and right products
    for (int i = 0; i < n; i++) {
        answer[i] = leftProduct[i] * rightProduct[i];
    }

    return answer;
}

Step-by-Step Execution: nums = [1,2,3,4]

Initial: nums = [1, 2, 3, 4]


Step 1: Build leftProduct array
═══════════════════════════════════════════════════════════════════
leftProduct[0] = 1  (no elements to left)

i=1: leftProduct[1] = leftProduct[0] * nums[0]
                    = 1 * 1 = 1

i=2: leftProduct[2] = leftProduct[1] * nums[1]
                    = 1 * 2 = 2

i=3: leftProduct[3] = leftProduct[2] * nums[2]
                    = 2 * 3 = 6

leftProduct = [1, 1, 2, 6]


Step 2: Build rightProduct array
═══════════════════════════════════════════════════════════════════
rightProduct[3] = 1  (no elements to right)

i=2: rightProduct[2] = rightProduct[3] * nums[3]
                     = 1 * 4 = 4

i=1: rightProduct[1] = rightProduct[2] * nums[2]
                     = 4 * 3 = 12

i=0: rightProduct[0] = rightProduct[1] * nums[1]
                     = 12 * 2 = 24

rightProduct = [24, 12, 4, 1]


Step 3: Multiply left and right products
═══════════════════════════════════════════════════════════════════
answer[0] = leftProduct[0] * rightProduct[0] = 1 * 24 = 24
answer[1] = leftProduct[1] * rightProduct[1] = 1 * 12 = 12
answer[2] = leftProduct[2] * rightProduct[2] = 2 * 4 = 8
answer[3] = leftProduct[3] * rightProduct[3] = 6 * 1 = 6

═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: [24, 12, 8, 6]
═══════════════════════════════════════════════════════════════════

⏰ Time: O(n) - three passes
💾 Space: O(n) - two extra arrays

---

✅ Approach 4: Space Optimized (O(1) Space - Optimal)

The Ultimate Optimization 💡

Core Logic:

Can we avoid extra leftProduct and rightProduct arrays?

Observation:
- Use the answer array itself to store left products first
- Then multiply by right products on the fly (using a variable)

Steps:
1. Fill answer array with left products
2. Scan right-to-left, maintaining running right product
3. Multiply answer[i] by running right product

Visual Process:

nums = [1, 2, 3, 4]

Step 1: Fill answer with left products
answer = [1, 1, 2, 6]

Step 2: Scan right-to-left with running rightProduct
rightProduct = 1 (start)

i=3: answer[3] = answer[3] * rightProduct = 6 * 1 = 6
     rightProduct = rightProduct * nums[3] = 1 * 4 = 4

i=2: answer[2] = answer[2] * rightProduct = 2 * 4 = 8
     rightProduct = rightProduct * nums[2] = 4 * 3 = 12

i=1: answer[1] = answer[1] * rightProduct = 1 * 12 = 12
     rightProduct = rightProduct * nums[1] = 12 * 2 = 24

i=0: answer[0] = answer[0] * rightProduct = 1 * 24 = 24
     rightProduct = rightProduct * nums[0] = 24 * 1 = 24

Final answer = [24, 12, 8, 6]

Why This is Better: - O(n) time - two passes - O(1) space - only output array - No extra arrays needed - Meets follow-up requirement!

Implementation

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

    // Step 1: Fill answer with left products
    answer[0] = 1;
    for (int i = 1; i < n; i++) {
        answer[i] = answer[i - 1] * nums[i - 1];
    }

    // Step 2: Multiply by right products
    int rightProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
        answer[i] = answer[i] * rightProduct;
        rightProduct *= nums[i];
    }

    return answer;
}

Step-by-Step Execution: nums = [1,2,3,4]

Initial: nums = [1, 2, 3, 4]


Step 1: Fill answer with left products
═══════════════════════════════════════════════════════════════════
answer[0] = 1  (no elements to left)

i=1: answer[1] = answer[0] * nums[0]
               = 1 * 1 = 1

i=2: answer[2] = answer[1] * nums[1]
               = 1 * 2 = 2

i=3: answer[3] = answer[2] * nums[2]
               = 2 * 3 = 6

After Step 1: answer = [1, 1, 2, 6]


Step 2: Multiply by right products (scan right-to-left)
═══════════════════════════════════════════════════════════════════
rightProduct = 1  (initialize)

i=3:
├─ answer[3] = answer[3] * rightProduct
│            = 6 * 1 = 6
└─ rightProduct = rightProduct * nums[3]
               = 1 * 4 = 4

i=2:
├─ answer[2] = answer[2] * rightProduct
│            = 2 * 4 = 8
└─ rightProduct = rightProduct * nums[2]
               = 4 * 3 = 12

i=1:
├─ answer[1] = answer[1] * rightProduct
│            = 1 * 12 = 12
└─ rightProduct = rightProduct * nums[1]
               = 12 * 2 = 24

i=0:
├─ answer[0] = answer[0] * rightProduct
│            = 1 * 24 = 24
└─ rightProduct = rightProduct * nums[0]
               = 24 * 1 = 24

═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: [24, 12, 8, 6]
═══════════════════════════════════════════════════════════════════

Another Example: nums = [-1,1,0,-3,3]

Step 1: Build left products in answer
═══════════════════════════════════════════════════════════════════
answer[0] = 1
answer[1] = 1 * (-1) = -1
answer[2] = -1 * 1 = -1
answer[3] = -1 * 0 = 0
answer[4] = 0 * (-3) = 0

answer = [1, -1, -1, 0, 0]


Step 2: Multiply by right products
═══════════════════════════════════════════════════════════════════
rightProduct = 1

i=4: answer[4] = 0 * 1 = 0, rightProduct = 1 * 3 = 3
i=3: answer[3] = 0 * 3 = 0, rightProduct = 3 * (-3) = -9
i=2: answer[2] = -1 * (-9) = 9, rightProduct = -9 * 0 = 0
i=1: answer[1] = -1 * 0 = 0, rightProduct = 0 * 1 = 0
i=0: answer[0] = 1 * 0 = 0, rightProduct = 0 * (-1) = 0

Result: [0, 0, 9, 0, 0] ✓

⏰ Time: O(n) - two passes
💾 Space: O(1) - excluding output array

---

🔍 Edge Cases

Case 1: Array with zero
Input: nums = [1,0,3]
Output: [0,9,0]
Strategy: Zero makes most products 0

Case 2: Multiple zeros
Input: nums = [0,0,3]
Output: [0,0,0]
Strategy: Multiple zeros make all products 0

Case 3: All ones
Input: nums = [1,1,1,1]
Output: [1,1,1,1]

Case 4: Negative numbers
Input: nums = [-1,2,-3,4]
Output: [-24,12,-8,6]
Strategy: Handle negative products correctly

Case 5: Two elements
Input: nums = [5,3]
Output: [3,5]

Case 6: Large products (within 32-bit)
Input: nums = [10,10,10,10]
Output: [1000,1000,1000,1000]

Case 7: Mixed positive and negative
Input: nums = [2,-3,4,-5]
Output: [60,-40,30,-24]

Case 8: Single zero in middle
Input: nums = [2,3,0,4,5]
Output: [0,0,120,0,0]

---

Common Mistakes

Mistake 1: Using division when there's a zero
❌ Wrong: totalProduct / nums[i] fails when nums[i]=0
✓ Right: Use left × right product approach

Mistake 2: Not initializing first element correctly
❌ Wrong: leftProduct[0] = nums[0]
✓ Right: leftProduct[0] = 1 (no elements to left)

Mistake 3: Wrong loop bounds
❌ Wrong: for (int i = 0; i < n; i++) for leftProduct
✓ Right: for (int i = 1; i < n; i++) (start from 1)

Mistake 4: Not updating rightProduct after using it
❌ Wrong: answer[i] *= rightProduct; (forget to update rightProduct)
✓ Right: answer[i] *= rightProduct; rightProduct *= nums[i];

Mistake 5: Integer overflow
❌ Wrong: Not considering product might overflow
✓ Right: Problem guarantees fit in 32-bit integer

Mistake 6: Modifying input array
❌ Wrong: Store products in nums array
✓ Right: Use separate answer array

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n²)
  Space: O(1)
  Use: Never (too slow)

Approach 2: Division
  Time: O(n)
  Space: O(1)
  Use: Not allowed by problem

Approach 3: Left & Right Arrays
  Time: O(n)
  Space: O(n)
  Use: Clear, understandable

Approach 4: Space Optimized (OPTIMAL)
  Time: O(n)
  Space: O(1)
  Use: Best solution, meets follow-up

🔑 The Core Insight

Key breakthrough:
answer[i] = (product left of i) × (product right of i)

Two-pass strategy:
Pass 1 (left-to-right): Build left products
Pass 2 (right-to-left): Multiply by right products

Space optimization:
→ Use answer array to store left products
→ Use variable to track running right product
→ Achieve O(1) extra space!

Why no division:
→ Division fails with zeros
→ Left × Right approach handles zeros naturally

🎯 Pattern Recognition

Problem Type: Array Product with Exclusion
Core Pattern: Prefix/Suffix Product

When to Apply:
✓ Need product of all elements except current
✓ Cannot use division
✓ Must handle zeros
✓ O(n) time required

Key Techniques:
→ Prefix product (left cumulative)
→ Suffix product (right cumulative)
→ Combine both for final answer
→ Space optimization with running variable

Related Problems:
- Maximum Product Subarray (LC 152)
- Range Sum Query (LC 303)
- Subarray Product Less Than K (LC 713)
- Maximum Product of Three Numbers (LC 628)

🧠 Interview Strategy

Step 1: "Need product of all except current element"
Step 2: "Division seems obvious but not allowed"
Step 3: "Key insight: left product × right product"
Step 4: "Build two arrays for left and right products - O(n) space"
Step 5: "Optimize: use answer array + variable - O(1) space!"

---

📝 Quick Revision Notes

🎯 Core Concept:

For each index, compute product of elements to its left × product of elements to its right. Use answer array to store left products, then multiply by running right product.

⚡ Quick Implementation:

public int[] productExceptSelf(int[] nums) {
    int len = nums.length;
    int[] res = new int[len];
    // Approach 0 - brute force. Take element by element and multiply with the rest.
    // Approach 1 - calculate overall product and divide each element. Handle /0
    // // Approach 2 - 2 separate left and right product arrays excluding the number
    // // find left product array        
    // int[] leftProducts = new int[len];        
    // int temp = 1;
    // leftProducts[0] = temp;
    // for(int i = 1; i < len; i++) {
    //     temp = temp * nums[i - 1];
    //     leftProducts[i] = temp;
    // }
    // // find right product array
    // int[] rightProducts = new int[len];
    // temp = 1;
    // rightProducts[len - 1] = temp;
    // for(int i = len - 2; i >= 0; i--) {
    //     temp = temp * nums[i + 1];
    //     rightProducts[i] = temp;
    // }
    // // find overall product array
    // for(int i = 0; i < len; i++) {
    //     res[i] = leftProducts[i] * rightProducts[i];
    // }

    // Approach 3 - using a single product array
    // find left product array        
    int[] leftProducts = new int[len];        
    int temp = 1;
    leftProducts[0] = temp;
    for(int i = 1; i < len; i++) {
        temp = temp * nums[i - 1];
        leftProducts[i] = temp;
    }
    temp = 1;
    for(int i = len - 1; i >= 0; i--) {
        res[i] = temp * leftProducts[i];
        temp = temp * nums[i];
    }

    return res;
}

🔑 Key Insights:

• answer[i] = leftProduct[i] × rightProduct[i]
• Two passes: left-to-right then right-to-left
• First pass: build left products in answer array
• Second pass: multiply by running right product
• No division needed - handles zeros naturally
• O(1) extra space (answer array doesn't count)
• Initialize: answer[0]=1 (no left elements), rightProduct=1
• Update rightProduct after using it: rightProduct *= nums[i]

🎪 Memory Aid:

"Left pass fills answer, right pass multiplies in!"
Think: "Two passes: build left, multiply right"

---

Related Patterns

• Maximum Product Subarray (LC 152)
• Range Sum Query - Immutable (LC 303)
• Subarray Product Less Than K (LC 713)

---

Happy practicing! 🎯