Question 227738 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – How to use Map/Set imporve the code to O(n)?

Maybe I should use Map/Set, but I can not work it out…

let items = [
  {type: 'a', name: 'a1', color: 'yellow'},
  {type: 'b', name: 'b1', color: 'orange'}
];
const excludes = [
  {k: 'color', value: 'yellow'},
  {k: 'name', value: 'x'}
];

excludes.forEach((exclude) => {
  items = items.filter((item) => item[exclude.k] !== exclude.value)
})

console.log(items)
Tags:

2

Answers


  1. 0

    You cannot avoid to read the input at least. That already costs O(n). So you need to check if an element needs to be excluded in O(1).

    The data structure that comes in mind that could do that (at least on average) is a Hash-Map.

    Login or Signup to reply.
  2. 0

    You can improve it by constructing a hashmap for excludes items, which takes O(n).

    Then filtering it takes O(m). so overall O(n+m) which is linear!

    let items = [
  {type: 'a', name: 'a1', color: 'yellow'},
  {type: 'b', name: 'b1', color: 'orange'}
];
const excludes = [
  {k: 'color', value: 'yellow'},
  {k: 'name', value: 'x'}
];

//Create a map for excludes by value
//Which takes O(n)

const excludesMap = excludes.reduce((acc, it) => {
  acc[it.value] = true;
  return acc;
}, {});


//Filter takes O(m)

const filteredItems = items.filter(it => !excludesMap[it.color]);
console.log(filteredItems);
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search