Product array Puzzle

The problem, simply

You get an array arr of n numbers. Build a new array prod where prod[i] is the product of all numbers in arr except arr[i].

You may not use division. That rule matters: with zeros in the array, "divide the total by arr[i]" breaks anyway.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each position, multiply all the other numbers.

1. For each i, start with p = 1.
2. For each j that is not i, multiply p by arr[j].
3. Store p in prod[i].

class Solution {
    public long[] productExceptSelf(int[] arr) {
        int n = arr.length;
        long[] prod = new long[n];
        for (int i = 0; i < n; i++) {
            long p = 1;
            for (int j = 0; j < n; j++) {
                if (j != i) p *= arr[j];      // everyone but me
            }
            prod[i] = p;
        }
        return prod;
    }
}

How long it takes: n products of n - 1 numbers each, O(n^2). Extra room: only the answer array, O(1) extra.

Way 2: the clever way

prod[i] = (product of everything left of i) x (product of everything right of i). Both parts can be built in one walk each.

1. Walk left to right with left = 1. Set prod[i] = left, then left *= arr[i]. Now prod[i] holds the left part.
2. Walk right to left with right = 1. Set prod[i] *= right, then right *= arr[i]. Now prod[i] holds left part x right part.

The order inside each step matters: write the whisper first, then multiply in your own card, so a number never counts itself.

class Solution {
    public long[] productExceptSelf(int[] arr) {
        int n = arr.length;
        long[] prod = new long[n];
        long left = 1;
        for (int i = 0; i < n; i++) {
            prod[i] = left;          // everything to my left
            left *= arr[i];          // then add my own card
        }
        long right = 1;
        for (int i = n - 1; i >= 0; i--) {
            prod[i] *= right;        // times everything to my right
            right *= arr[i];
        }
        return prod;
    }
}

How long it takes: two walks, O(n). Extra room: two numbers. The answer array does not count as extra, so O(1).

Watch out for

• Updating left before writing prod[i]. Then each number multiplies itself in.
• Products overflow fast. Use long, or BigInteger if the numbers and the length are large, or take answers modulo a prime if the problem says so.
• An array of one number gives [1].
• Keeping two extra arrays leftProd and rightProd works too and is easier to explain first, but it costs O(n) extra room.

What interviewers ask next

• Do it with division but handle zeros. Count zeros and multiply the nonzero numbers: zero zeros means total / arr[i], one zero means only the zero's spot gets the product, two or more means all zeros.
• The same idea with sums instead of products is just total - arr[i]. Products are interesting because of division and zeros.
• Answers modulo a prime with zeros allowed: use the prefix and suffix way, since modular division by 0 does not exist.
• Where else do left and right sweeps help? Trapping rain water (tallest wall to the left and right) and candy distribution (one pass each way).

Remember this

Grown-up words: the left whispers are prefix products, the right whispers are suffix products, and "the answer array does not count" is the usual rule for O(1) auxiliary space.