Product of array except self

For every index, multiply the product of everything to its left by the product of everything to its right. No division needed.

The idea

Fill res[i] with the product of everything to its left in one left-to-right pass. Then sweep right-to-left, multiplying in a running "suffix" product of everything to the right. Combining the two avoids ever dividing by a[i], so it still works if a value were zero.

Code

public static int[] ProductExceptSelf(int[] a) {
    int n = a.Length;
    var res = new int[n];
    res[0] = 1;
    for (int i = 1; i < n; i++)
        res[i] = res[i - 1] * a[i - 1];
    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) {
        res[i] *= suffix;
        suffix *= a[i];
    }
    return res;
}

Tips

• res[0] has nothing to its left, so it starts at 1; the same holds in reverse for the last index and the suffix sweep.
• The dividing approach (multiply everything, then divide by a[i]) is shorter but breaks the moment any value is zero.

In the .NET library

Both passes read and write the same res array, so the only extra variable is suffix itself - the output array does not count toward the space bound.