JavaScript - filter array of objects by content of primitive array in O(n)

Question

I have the following array of objects:

[{
  itemType: 'bottle',
  itemId: '111'
}, {
  itemType: 'bottle',
  itemId: '222'
}, {
  itemType: 'bottle',
  itemId: '333'
}]

I'm trying to filter (time complexity of O(n)) it by a simple array like the following:

[ '111', '333' ]

So the final array of objects looks like this:

[{
  itemType: 'bottle',
  itemId: '222'
}]

I thought using underscoreJS but there's no builtin function to accomplish this in a simple manner. Any other options?

Iterate over the source array, use a set for the IDs to remove. This requires a different data structure for what to remove, but keeps you to a single iteration and it's still O(n). — Dave Newton, Sep 28 '16 at 14:22

score 2 · Answer 1 · edited Jan 06 '17 at 07:20

2

Assume that

var a = [{
    itemType: 'bottle',
    itemId: '111'
},
 {
    itemType: 'bottle',
    itemId: '222'
},
{
    itemType: 'bottle',
    itemId: '333'
}]

AND

var b = [ '111', '333' ]

So using underscore methods this can be simply done:

_.filter(a, function(ele) {
    return !_.contains(b, ele.itemId)
})

edited Jan 06 '17 at 07:20

J. Chomel

8,193
15
41
69

answered Jan 06 '17 at 07:04

Vijayraj

193
1
5

Seth Holladay · Answer 2 · 2017-01-06T07:42:53.493

By using a Set for the blacklist we can remove duplicates and save lookup time.

const blacklist = new Set(['111', '333']);
const items = [
    {
        itemType : 'bottle',
        itemId   : '111'
    },
    {
        itemType : 'bottle',
        itemId   : '222'
    },
    {
        itemType : 'bottle',
        itemId   : '333'
    }
];

const filtered = items.filter((item) => {
    return !blacklist.has(item.itemId);
});

In the above code, filtered is an array of items objects whose itemId does not appear on the blacklist.

nem035 · Accepted Answer · 2017-01-06T07:56:31.183

If you want a linear complexity solution you must tradeoff some space complexity to be able to perform a single linear search through the array. What you can do is convert your array of matches into a set, reducing the id existence lookup from O(ids.length) to O(1) and thus reducing your total complexity from O(arr.length*ids.length) to O(arr.length) + O(ids.length):

If you cannot tradeoff any space, your total complexity will be quadratic: O(arr.length * ids.length).

ES6 solution O(arr.length) + O(ids.length):

const arr = [{itemType: 'bottle', itemId: '111'},{itemType: 'bottle', itemId: '222'},{itemType: 'bottle', itemId: '333'}];
const ids = ['111', '333'];

function filter(arr, ids) {
  const s = new Set(ids); // O(ids.length) to build the set and use O(ids.length) space
  return arr.filter(item => s.has(item.itemId)); // O(arr.length) to filter the array
}

console.log(filter(arr, ids));

ES5 solution O(arr.length) + O(ids.length):

var arr = [{itemType: 'bottle', itemId: '111'},{itemType: 'bottle', itemId: '222'},{itemType: 'bottle', itemId: '333'}];
var ids = ['111', '333'];

function filter(arr, ids) {
  // O(ids.length) to build the set and use O(ids.length) space
  var s = ids.reduce(function(s, id) {
    s[id] = true;
    return s;
  }, Object.create(null));

  // O(arr.length) to filter the array
  return arr.filter(function(item) {
    return s[item.itemId];
  });
}

console.log(filter(arr, ids));

JavaScript - filter array of objects by content of primitive array in O(n)

3 Answers3