Given an array arr[] of n integers, construct a Product Array prod[] (of same size) such that prod[i] is equal to the product of all the elements of arr[] except arr[i]. Solve it without division.

Overview

Brute Force

It is recommended to start solving algorithms with a brute force approach and from there try to find an optimal solution.

Brute Force Time Complexity

We have a nested loop in this solution that leads to a O(n^2), not ideal. Also there are tons of repeated multiplication that highlight the inefficiency of this solution.

Brute Force Space Complexity

Space complexity is O(n), as we are creating a new array of size n that contains the results if the solution.

Brute Force Java Source Code

    public int[] arrayOfProductsBruteForce(int[] array) {
        var result = new int[array.length];

        for(var i=0;i<array.length;i++) {
            var product=1;

            for(var j=0;j<array.length;j++) {
                if(i!=j) {
                    product = product*array[j];
                }
            }
            result[i] = product;
        }
        return result;
    }

Optimal Solution - Using a Left/Right array

Each result element is simply the product of all left elements times the product of all right elements. This solution does not need a nested loop and is a huge performance improvement vs the brute force solution.

Left/Right array

Left/Right array Time Complexity

The algorithm is solved in linear time of O(n). We have three loops that iterate through arrays of size n.

Left/Right array Space Complexity

Space complexity is O(n), as we are creating three new arrays:

• Left Array
• Right Array
• Result Array

Left/Right array Java Source Code

    public int[] arrayOfProductsLeftRight(int[] array) {
        var left = new int[array.length];
        var right = new int[array.length];
        var result = new int[array.length];

        Arrays.fill(left,1);
        Arrays.fill(right,1);
        Arrays.fill(result,1);

        var product = 1;
        for (var i=0;i<left.length;i++) {
            left[i] = product;
            product=product*array[i];
        }

        product = 1;
        for (var i=right.length-1;i>=0;i--) {
            right[i] = product;
            product=product*array[i];
        }

        for(var i=0;i<result.length;i++) {
            result[i] = left[i]*right[i];
        }

        return result;
    }

Optimal Solution - In place calculation of Left Right Array

Left array only overview

Left array only Java Source code

    public int[] arrayOfProductsLeftOnly(int[] array) {
        var result = new int[array.length];

        Arrays.fill(result,1);

        var product = 1;
        for (var i=0;i<result.length;i++) { //setup like a left array
            result[i] = product;
            product=product*array[i];
        }


        product = 1;
        for (var i=result.length-1;i>=0;i--) {
            result[i] = result[i] * product;
            product = product*array[i];
            System.out.println("i = "+i+" product = "+product+" array[i]="+array[i]);

        }

        return result;
    }

Left array only Time Complexity

The algorithm is solved in linear time of O(n). We have two loops that iterate through the array of size n.

Left array only Space Complexity

Space complexity is O(n), as we are creating two new arrays.

Conclusion

Doing linear scans over an associative array is like trying to club someone to death with a loaded Uzi.

Larry Wall