Array of Array products[Medium] (Pramp, Java)

Problem Description: Given an array of integers arr, you’re asked to calculate for each index i the product of all integers except the integer at that index (i.e. except arr[i]). Implement a function arrayOfArrayProducts that takes an array of integers and returns an array of the products.

Solve without using division and analyze your solution’s time and space complexities.

Examples:

input:  arr = [8, 10, 2]
output: [20, 16, 80] # by calculating: [10*2, 8*2, 8*10]
input:  arr = [2, 7, 3, 4]
output: [84, 24, 56, 42] # by calculating: [7*3*4, 2*3*4, 2*7*4, 2*7*3]

Constraints:

• [time limit] 5000ms
• [input] array.integer arr
• 0 ≤ arr.length ≤ 20
• [output] array.integer

Approach: We multiply all values of arr before and after each index, we get our answer — the product of all the integers except arr[i].

Let me explain it with an example.

Given numbers [2, 7, 3, 4], regarding the third number 3, the product of array except 3 is 2*7*4 which consists of two parts: left 2*7 and right 4 . The product is left*right. We can get lefts and rights:

Numbers:     2    7   3    4
Lefts:            2  2*7 2*7*3
Rights:  7*3*4  3*4   4

Let’s fill the empty with 1:

Numbers:     2    7   3    4
Lefts:       1    2  2*7 2*7*3
Rights:  7*3*4   3*4  4    1

Solution:

public int[] arrayOfArrayProducts(int[] arr) 
{
   int n=arr.length;
   if(n==0 || n==1) return new int[0];
   int[] result = new int[n];
// Calculate lefts and store in result.
   int left= 1;
   for(int i=0; i<n; i++)
   {
     result[i] = left;
     left *= arr[i];
   }
// Calculate rights and the product from the end of the array.
   int right =1;
   for(int i=n-1; i>=0; i--)
   {
      result[i] *= right;
      right *= arr[i];
   }
  return result; 
 }

Time & Space Complexity: We can calculate lefts and rights in 2 loops. The time complexity is O(n).

We store lefts in result array. If we allocate a new array for rights. The space complexity is O(n). To make it O(1), we just need to store it in a variable which is right.

#interviewpreparation #technicalinterview #coding #problemsolving