CODEWITHSUNDEEP
javascriptalgorithm
devdropper87
devdropper87

Reputation: 4187

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

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.

Upvotes: 0

Views: 540

Answers (3)

Amit
Amit

Reputation: 46323

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.

Upvotes: 2

Anchalee
Anchalee

Reputation: 666

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;
}

Upvotes: 2

Nicolas Husson
Nicolas Husson

Reputation: 34

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

Upvotes: -1

Related Questions