Product array Puzzle

Problem Statement

Given an array of integers, construct a Product Array such that prod[i] is equal to the product of all elements of arr except arr[i].

Constraints:

• Solve without using the division operator
• Array may contain zeros
• Handle negative numbers

Example:

• Input: arr = [10, 3, 5, 6, 2]
• Output: [180, 600, 360, 300, 900]
• Explanation:
  • prod[0] = 3 × 5 × 6 × 2 = 180
  • prod[1] = 10 × 5 × 6 × 2 = 600
  • prod[2] = 10 × 3 × 6 × 2 = 360
  • prod[3] = 10 × 3 × 5 × 2 = 300
  • prod[4] = 10 × 3 × 5 × 6 = 900

Approach 1: Brute Force (Double Loop)

Intuition

For each element, multiply all other elements.

Algorithm

1. For each index i
2. Multiply all elements except arr[i]
3. Store result in prod[i]

public class Solution {
    public long[] productArray(int[] arr) {
        int n = arr.length;
        long[] prod = new long[n];
        java.util.Arrays.fill(prod, 1);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    prod[i] *= arr[j];
                }
            }
        }
        
        return prod;
    }
}

Complexity Analysis

• Time Complexity: O(n²) - Nested loops
• Space Complexity: O(n) - Output array

Approach 2: Using Division (If Allowed)

Intuition

Calculate total product, then divide by each element.

Note: This doesn't work if array contains zeros.

Handling Zeros with Division

Approach 3: Prefix and Suffix Products (Optimal)

Intuition

For each index i, the product of all elements except arr[i] equals: (product of all elements to the left of i) × (product of all elements to the right of i)

Algorithm

1. Create left[] where left[i] = product of elements from 0 to i-1
2. Create right[] where right[i] = product of elements from i+1 to n-1
3. Result: prod[i] = left[i] × right[i]

public class Solution {
    public long[] productArray(int[] arr) {
        int n = arr.length;
        
        long[] left = new long[n];
        long[] right = new long[n];
        long[] prod = new long[n];
        
        // Initialize
        java.util.Arrays.fill(left, 1);
        java.util.Arrays.fill(right, 1);
        
        // Calculate left products
        for (int i = 1; i < n; i++) {
            left[i] = left[i - 1] * arr[i - 1];
        }
        
        // Calculate right products
        for (int i = n - 2; i >= 0; i--) {
            right[i] = right[i + 1] * arr[i + 1];
        }
        
        // Calculate final products
        for (int i = 0; i < n; i++) {
            prod[i] = left[i] * right[i];
        }
        
        return prod;
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n) - Three passes
• Space Complexity: O(n) - Two auxiliary arrays

Approach 4: Space Optimized (Optimal)

Intuition

Store left products in the result array, then calculate right products on-the-fly.

public class Solution {
    public long[] productArray(int[] arr) {
        int n = arr.length;
        long[] prod = new long[n];
        java.util.Arrays.fill(prod, 1);
        
        // Calculate left products and store in prod
        long leftProduct = 1;
        for (int i = 0; i < n; i++) {
            prod[i] = leftProduct;
            leftProduct *= arr[i];
        }
        
        // Multiply with right products
        long rightProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            prod[i] *= rightProduct;
            rightProduct *= arr[i];
        }
        
        return prod;
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n) - Two passes
• Space Complexity: O(1) - Only output array (not counting output)

Handling Edge Cases

Key Takeaways

1. No Division: Prefix-suffix product approach avoids division
2. Space Optimization: Use output array to store intermediate results
3. Two Pass Solution: First pass for left products, second for right products
4. Handles Zeros: Works correctly with zeros in array
5. Overflow Consideration: Use long long for large products
6. O(1) Extra Space: Optimal solution uses only output array