Coding Problem: Array of Products

In this blog post, we will write a program for Array of Products problem.

Problem Statement:

Write a method that takes in a non-empty array of integers and returns an array of same length, where each element in the output array is equal to the product of every other number in the input array.

In other words, the value of output[i] is equal to the product of every number in the input array other than input[i].

Note that you're expected to solve this problem without using division.

Sample Input:

array = [5, 1, 4, 2]

Sample Output:

[8, 40, 10, 20]

Solution:

Method 1: Naive Solution, use two nested loops

We can use two for loops and for every iteration of outer loop, iterate through all the elements in inner loop and check if outer loop and inner loop index matches, if it doesn't match we multiply and continue.

Time Complexity: O(n²)

Space Complexity: O(n)

where n is the length of the input array. 

public class ProductsArray {

    public int[] arrayOfProducts(int[] array) {
        int[] products = new int[array.length];

        for (int i = 0; i < array.length; i++) {
            int runningProduct = 1;
            for (int j = 0; j < array.length; j++) {
                if (i != j) {
                    runningProduct *= array[j];
                }
                products[i] = runningProduct;
            }
        }

        return products;
    }
}

Method 2: 

For each index in the input array, try calculating the product of every element to the left and the product of every element to the right. You can use two loops through the array: one from left to right and another from right to left.

Steps:

• Create a products array of same length as input array.
• Initialize a variable as left running product to 1.
  • Iterate through the array elements from left to right.
  • For each iteration update the products array at that index with left running product and update the left running product by multiplying itself with array element.
• Now you have got products array which is multiplied from left.
• Initialize a variable as right running product to 1.
  • Iterate through the array elements from right to left.
  • For each iteration update the products array by multiplying itself with right running product and update the right running product by multiplying itself with array element.

Time Complexity: O(n)

Space Complexity: O(n)

where n is the length of the input array. 

public class ProductArray {

    /**
     * For each index in the input array, try calculating the product
     * of every element to the left and the product of every element
     * to the right.
     * @param array non-empty array of integers
     * @return product array
     */
    public int[] arrayOfProducts(int[] array) {
        int[] products = new int[array.length];

        int leftRunningProduct = 1;
        for (int i = 0; i < array.length; i++) {
            products[i] = leftRunningProduct;
            leftRunningProduct *= array[i];
        }

        int rightRunningProduct = 1;
        for (int i = array.length - 1; i >= 0; i--) {
            products[i] *= rightRunningProduct;
            rightRunningProduct *= array[i];
        }

        return products;
    }

}