Product of Array Except Self

📌 Definition:

📖 Detailed Explanation:

Compute prefix products left-to-right into the result, then multiply by suffix products right-to-left with a running variable. This gives each element the product of everything except itself in O(n) time and O(1) extra space (besides the output). Division is banned because a zero element would break it.

💻 Solutions:

• Java
• JavaScript
• Python

public static int[] productExceptSelf(int[] a) {
    int n = a.length;
    int[] res = new int[n];
    res[0] = 1;
    for (int i = 1; i < n; i++) res[i] = res[i - 1] * a[i - 1];
    int right = 1;
    for (int i = n - 1; i >= 0; i--) { res[i] *= right; right *= a[i]; }
    return res;
}

function productExceptSelf(a) {
  const n = a.length, res = new Array(n).fill(1);
  for (let i = 1; i < n; i++) res[i] = res[i - 1] * a[i - 1];
  let right = 1;
  for (let i = n - 1; i >= 0; i--) { res[i] *= right; right *= a[i]; }
  return res;
}

def product_except_self(a):
    n = len(a)
    res = [1] * n
    for i in range(1, n):
        res[i] = res[i - 1] * a[i - 1]
    right = 1
    for i in range(n - 1, -1, -1):
        res[i] *= right
        right *= a[i]
    return res

🔑 Key Points:

• Prefix pass then suffix pass
• No division (handles zeros correctly)
• O(1) extra space using the output array
• O(n) time

🌍 Real-World Example: