About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Array Product Problem

Given an array of numbers nums of size n, find an array of numbers products of size n, such that products[i] is the product of all numbers nums[j], where j != i.

Example One

Input:

5

1

2

3

4

5

Output:

120

60

40

30

24

Resultant Product array products = [products[0], products[1], products[2], products[3], products[4]]

= [(nums[1]*nums[2]*nums[3]*nums[4]), (nums[0]*nums[2]*nums[3]*nums[4]), (nums[0]*nums[1]*nums[3]*nums[4]), (nums[0]*nums[1]*nums[2]*nums[4]), (nums[0]*nums[1]*nums[2]*nums[3])]

= [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]

= [120, 60, 40, 30, 24]

Example Two

Input:

3

4

9

10

Output:

90

40

36

Resultant Product array products = [products[0], products[1], products[2]]

= [(nums[1]*nums[2]), (nums[0]*nums[2]), (nums[0]*nums[1])]

= [(9*10), (4*10), (4*9)]

 = [90, 40, 36] 

Notes

Input Parameters: There is only one argument: nums, denoting input array.

Output: Return an array of numbers products, denoting the required product array where products[i] is the (product of all numbers nums[j]) % (10^9 + 7), where j != i.

Constraints:

• You can't use division anywhere in solution.

• 2

• -10^9

• products[i] >=0, i = 0, 1, 2, ... , n-1

• You are allowed to use only constant extra space and the resultant product array will not be considered extra space.

Usage of resultant products array will not be considered as extra space used. Without using division is the key constraint to remember.

Solutions

Are you getting a wrong answer for some of the test cases, but still think your logic is correct?

Check for the overflow.

If a = 10^9, b = 10^9 and we do, int c = (a * b) % (10^9 + 7), then it will overflow. Instead, use something like int c = (a * (long long int) 1 * b) % (10^9 + 7), to avoid overflow. By multiplying with (long long int) 1, we make sure that the calculation is done in long long int, instead of int.

We provided two solutions.

1) brute_force_solution.java

A naive approach would be to find the i-th element of the output array (i.e. products[i]), iterate over the entire input array to get the product of all elements nums[j], such that j != i.

Time Complexity:

O(n*n) where n is length of the input array. As we are iterating over the entire array to find products[i] and as it can be 0

Auxiliary Space Used:

O(1).

As we are not storing anything extra and excluding space used to store output array products.

Space Complexity:

O(n) where n is length of the input array.

Storing the input array will take O(n) and auxiliary space used is O(1). So, O(n) + O(1) → O(n). 


 // -------- START --------
    static int mod = (int)Math.pow(10, 9) + 7;
    static int[] getProductArray(int[] nums) {
        // Size of output array is same as that of input array
        int[] products = new int[nums.length];

        for (int currentIndex = 0; currentIndex < nums.length; currentIndex++) {
            products[currentIndex] = 1;
            for (int iterator = 0; iterator < nums.length; iterator++) {
                if (iterator != currentIndex) {
                    nums[iterator] = nums[iterator]>0?(nums[iterator]%mod):((mod+nums[iterator])%mod);
                    products[currentIndex] = (int)((products[currentIndex] * 1l * nums[iterator])%mod);
                }
            }
        }

        return products;
    }
    // -------- END --------


2) optimal_solution.java

Notice that for products[i], product of all input array elements other than i-th element is nothing but (product of all elements nums[j], 0

So, iterate over the input array twice to fill output array products, once for updating products[i] with (nums[0] * nums[1] *...*nums[i-1]), and next one for updating products[i] with (nums[i+1] * nums[i+2] * … * nums[n-1]).

Time Complexity:

O(n) where n is the length of the input array.

As we are iterating over the input array two times it will take O(n).

Auxiliary Space Used:

O(1).

We are not storing anything extra.

Space Complexity:

O(n) where n is the length of the input array.

Storing the input array will take O(n) and the auxiliary space used is O(1). So, O(n) + O(1) → O(n). 


// -------- START --------
    static int mod = (int)Math.pow(10, 9) + 7;
    static int[] getProductArray(int[] nums) {

        // Size of output array is same as that of input array
        int[] products = new int[nums.length];

        // For finding value of products[i], product of all nums elements 
        // other than ith element is nothing but
        // (product of all nums[j], 0<=j<=(i-1)) * (product of all nums[j], (i+1)<=j<=(nums.length-1))
        // i.e. (nums[0]*nums[1]*...*nums[i-1]) * (nums[i+1]*nums[i+2]*...*nums[nums.length-1])

        int leftProduct = 1;

        // Filling products, such that products[i] contains 
        // product of all elements nums[j], 0<=j<=(i-1)
        for (int currentIndex = 0; currentIndex < nums.length; currentIndex++) {
            // Here, leftProduct contains product of all elements
            // nums[j], 0<=j<=(currentIndex-1)
            products[currentIndex] = leftProduct;

            // After this updation of leftProduct, leftProduct contains product of all
            // elements nums[j], 0<=j<=currentIndex
            nums[currentIndex] = nums[currentIndex]>0?nums[currentIndex]:(mod+nums[currentIndex])%mod;   
            leftProduct = (int)((leftProduct * 1l * nums[currentIndex])%mod);        
        }

        int rightProduct = 1;

        // Updating products, such that products[i] contains new value
        // ((products[i]) * (product of all elements nums[j], 0<=j<=(i-1)))
        for (int currentIndex = nums.length - 1; currentIndex >= 0; currentIndex--) {
            // Here, rightProduct contains product of all elements
            // nums[j], (currentIndex+1)<=j<=(nums.length-1)
            products[currentIndex] = (int)((products[currentIndex] * 1l * rightProduct)%mod);

            // after this updation of rightProduct, rightProduct contains product of all
            // elements nums[j], currentIndex<=j<=(nums.length-1) 
            rightProduct = (int)((rightProduct * 1l * nums[currentIndex])%mod);
        }
        return products;
    }
    // -------- END --------


Attend our Free Webinar on How to Nail Your Next Technical Interview