efficient way to flatten array elements (not the whole array) javascript

Question

I'm practicing algorithms and am doing a problem where you are given an array and you want to return an array with the product of all other numbers except the number at that index. so [1, 2, 3, 4] would return [24, 12, 8, 6]. My approach was to loop through the array, make a copy, and splice out the current index, then push that copy to an output array.

function getAllProductsExceptAtIndex(arr) {
  var productArr = [];

  for (var i = 0; i < arr.length; i++) {
    var copy = arr.slice();
    copy.splice(i, 1);
    productArr[i] = copy;
  }

  // return productArr;
  for (var j = 0; j < productArr.length; j++) {

    reduce(productArr[j]); 

  }
}

getAllProductsExceptAtIndex([1, 2, 3]); ---> productArr = [[2,3],[1,3],[1,2]]

Now you have an output array with the correct values in it, it just needs to be "reduced" to one value with multiplication. now reduce is groovy and all, but in this case I'm trying to be efficient (time-wise) and so looping through an array and reducing would be o(n) squared since reduce uses a for loop internally. I thought of writing a helper to reduce but if you call it in the loop is it still o(n)squared?

What's a more efficient way to multiply the elements inside each index of productArr, and then flatten? would prefer not to use division in the solution.

Please don't change your question after an answer has been provided. That's bad behavior. — Amit
– Amit, Commented Nov 5, 2015 at 23:54
I don't know how to answer that, but I provided a non dividing solution as well. Maybe you can edit the question such that you prefer not using division (and mark that as an afterthought) - at least that doesn't make answers seem irrelevant. — Amit
– Amit, Commented Nov 6, 2015 at 0:03
I just now realized you were looking for an O(n) Time solution... added that too :-) — Amit
– Amit, Commented Nov 6, 2015 at 0:32

Anchalee · Accepted Answer · 2015-11-05 23:58:45Z

2

This solution is translated to JS from Interview Cake. Highly recommended for studying algorithms: https://www.interviewcake.com/

"To find the products of all the integers except the integer at each index, we'll go through our a list greedily twice. First we get the products of all the integers before each index, and then we go backwards to get the products of all the integers after each index.

When we multiply all the products before and after each index, we get our answer—the products of all the integers except the integer at each index!"

function productOfInts(arr){
  var productOfAllExceptIndex = new Array(arr.length);
  var productSoFar = 1;

  for (var i = 0; i < arr.length; i++){
    productOfAllExceptIndex[i] = productSoFar;
    productSoFar *= arr[i];
  }

  productSoFar = 1;

  i -= 1;

  while (i >= 0){
    productOfAllExceptIndex[i] *= productSoFar;
    productSoFar *= arr[i];
    i--;
  }

  return productOfAllExceptIndex;
}

answered Nov 5, 2015 at 23:58

Anchalee

6961 gold badge6 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

devdropper87 Over a year ago

Thanks! What is the mechanism by which you are "skipping" the current item?

devdropper87 Over a year ago

it's unclear to me how when you calculate the products before, productSoFar *= arr[i]; leads to productsBefore[0] = 1 and not producesBefore[0] = 2 when you give this function an input [2,4,10]

devdropper87 Over a year ago

nevermind, I got it - edited your answer to clarify the source of my confusion & the solution

Amit · Accepted Answer · 2015-11-06 07:01:46Z

2

Quite simple really:

function getAllProductsExceptAtIndex(arr) {
  var product = arr.reduce(function(prev, curr) { return prev * curr; });
  return arr.map(function(v) { return product / v; });
}

console.log(getAllProductsExceptAtIndex([1, 2, 3, 4]));

Calculate the product of the entire array, then map each value to product / current_value, which is the product of the rest of the array.

If you want a solution that doesn't use division, you can put the reduce inside the map and ignore the current item:

function getAllProductsExceptAtIndex(arr) {
  return arr.map(function(v, i) {
    return arr.reduce(function(prev, curr, j) {
      return i != j ? prev * curr : prev;
    });
  });
}

console.log(getAllProductsExceptAtIndex([1, 2, 3, 4]));

Finally, at the cost of complicating the code a little bit, we can do that in O(n) time:

function getAllProductsExceptAtIndex(arr) {
  if(arr.length === 0)
    return [];

  var i, products = [1];
  for(i = 0; i < arr.length - 1; i++) {
    products.push(products[i] * arr[i]);
  }

  for(var t = 1; i >= 0; i--) {
    products[i] *= t;
    t *= arr[i];
  }

  return products;
}

console.log(getAllProductsExceptAtIndex([1, 2, 3, 4]));

Here we're calculating the product to the left of each index in the first pass, but we're using previous calculation to do so (O(n)). Then we do the same thing backwards, calculating the product to the right and multiplying by what we calculated before. There's a constant "1" inserted in the edge cases - the "product" of 0 items (to the left of [0], and to the right of [length - 1]).

To see why this works, think of what it means to duplicate the product of all items on the left by the product of all items on the right of any item.

edited Nov 6, 2015 at 7:01

answered Nov 5, 2015 at 23:51

Amit

46.5k9 gold badges84 silver badges114 bronze badges

2 Comments

zerkms Over a year ago

"Finally, at the cost of complicating the code a little bit, we can do that in O(n) time:" --- the first 2-line solution is O(N) as well.

Amit Over a year ago

@zerkms - yes, but OP then added a constraint not to use division.

Nicolas Husson · Accepted Answer · 2015-11-05 23:55:22Z

-1

For array/object manipulation, you may use underscore or lodash https://lodash.com

// _.map : Produces a new array of values by mapping each value in list through a transformation function (iteratee)  http://underscorejs.org/#map 
_.map([1,2,3], function(value, index, collection){
  return _.without(collection, value)
}) // -> [[2,3],[1,3],[1,2]]

And if you like this lib, check also is.js and string.js

answered Nov 5, 2015 at 23:55

Nicolas Husson

542 bronze badges

Collectives™ on Stack Overflow

efficient way to flatten array elements (not the whole array) javascript

3 Answers 3

3 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related