DEV Community

Akhil
Akhil

Posted on

Product of array except self, a mind-boggling Google Interview question

Question: Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Eg :

   Input:  [1,2,3,4]
   Output: [24,12,8,6]
Enter fullscreen mode Exit fullscreen mode

Seems pretty easy right? Just multiply all the numbers then divide each one to get the result.

Here's the Google twist

Solve it without division and in O(n) time.

At first I was bit intermediate and I spent a lot of time figeuring it out but the solution is straight forward.

Tip: Always remember this principle

KEEP IT SIMPLE STUPID

End result is, for an index i we want product of all elements from 0 to i-1 and i+1 to n

So let's divide our problem into two sub-problems:

1> Find the product of all elements less than the current element.
2> Find the product of all elements greater than the current element.

The product of these two subproblems will give us the final result.

So for all elements less than i, let's keep it in array called left[];

 left[]=      1      1*arr[0]   1*arr[0]*arr[1]     1*arr[0]*arr[1]*arr[2]
            arr[0]     arr[1]        arr[2]                  arr[3]
Enter fullscreen mode Exit fullscreen mode

converting it to code:

   let left = [];
   let mul = 1;                 //keeping track of multiplication
   for(let i=0;i<nums.length;i++){
       left[i] = mul;
       mul = mul*nums[i];
   }
Enter fullscreen mode Exit fullscreen mode

Similarly for elements more than the current element. let's call it right[]

 right[]= 1*arr[1]*arr[2]*arr[3]   1*arr[2]*arr[3]       1*arr[3]       1
              arr[0]                  arr[1]              arr[2]      arr[3]     
Enter fullscreen mode Exit fullscreen mode

Converting that to code :

   let right = [];
   let mul = 1;                 //keeping track of multiplication
   for(let i=nums.length-1;i>=0;i++){
       right[i] = mul;
       mul = mul*nums[i];
   }
Enter fullscreen mode Exit fullscreen mode

After this, the only step is to put the two arrays together.

   let res = [];
   for(let i=0;i<nums.length;i++){
       res[i] = left[i]*right[i];
   }
   return res;
Enter fullscreen mode Exit fullscreen mode

Now, let's optimize this, here we're using 3 arrays in total, one for all elements less than i, one for all elements greater than i, and one for the final result.

Let's trim some fat and reduce this to a single array.

We have iterate twice on the array, one from left to right to get the multiplication of all elements less than the current index and once from right to left to get multiplication of all elements greater than the current index one.

Cinverting it to code :

var productExceptSelf = function(nums) {
    let res = [];
    let left = 1;
    let right = 1;
    for(let i=0;i<nums.length;i++){
        res[i] = left;
        left = left*nums[i];
    }

    for(let i=nums.length-1;i>=0;i--){
        res[i] = right*res[i];
        right = right*nums[i];
    }
    return res;
};
Enter fullscreen mode Exit fullscreen mode

I hope you liked my explanation :)

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/productExceptSelf.js

Latest comments (9)

Collapse
 
nadamuhammad28 profile image
Nada Omran

the time complexity isn't o(n),is it?
var productExceptSelf = function (nums) {
let l = 0;
let r = nums.length - 1;
let op = [];
for (let i = 0; i < nums.length; i++) {
let calc = 1;

while (r >= 0) {
  if (r !== l) {
    calc *= nums[r];
  }
  r--;
}
op[l] = calc;
r = nums.length - 1;
l++;
Enter fullscreen mode Exit fullscreen mode

}
return op;
};

Collapse
 
bitdweller profile image
Pedro Pimenta • Edited

EDIT: I guess I don't know what O(n) is? :)

I am probalby not understanding something, but wouldn't this work?

const baseArray = [1, 2, 3, 4]
const newArray = []

console.log(baseArray)

for (let i in baseArray) {
  let total = 1
  for (let p in baseArray) {
    if (i !== p) {
      total = total * baseArray[p]
    } 
  }
  newArray.push(total)
}

console.log(newArray)

I did it here: jsbin.com/zawuwugagu/edit?js,console

Collapse
 
akhilpokle profile image
Akhil

It works, but your algorithm works in O(n^2). The solution in article works in O(n).

Collapse
 
bitdweller profile image
Pedro Pimenta

Yeah I get it now. I'm not a programmer by education, so I don't know many of these concepts. I guess O(n) means going through the array only once, right? I go through the array as many times as elements are in the array, hence O(n^2). This is not performant, your solution (and the one asked for, actually) is resolved quicker and with less processing power. Hey, I learned something, right? :D Thanks!

Thread Thread
 
akhilpokle profile image
Akhil

Spot on! I will add your solution too so that people like you can get a better idea about performance :D

Collapse
 
balbuenac profile image
Carlos Balbuena

Cool explanation. But getting this result quickly in an interview is challenging

Collapse
 
akhilpokle profile image
Akhil

yea, I had to spend like 30 mins figuring out which data structure to use, and other random ideas. Some of the questions like these can be solved only if candidate has already seen something similar before.

Collapse
 
balbuenac profile image
Carlos Balbuena

Agree with you. But maybe we need to memorize / learn patterns instead of solutions. Thats what im doing now to prepare for my next interviews

Thread Thread
 
akhilpokle profile image
Akhil

Yea, that's why I am solving as many questions as possible. I would rather solve 400+ questions than depending on my thinking and thought process to come up with a solution within 30 mins.

An upside to this is that I am able to see many techniques that are being applied in real life like how basic graph algorithms work on navigation apps etc.