How to exclude elements from an array based on a Map while maintaining O(n)?

Question

I am trying to exclude some elements from array items that include properties from array excludes. I wrote this code which works fine. However, due to nested iterations, time complexity is O(n^3). Is there a way to do better?

const items = [
  { color: 'red', type: 'tv', age: 18 },
  { color: 'silver', type: 'phone', age: 20 },
  { color: 'blue', type: 'car', age: 18 },
  { color: 'green', type: 'tv', age: 10 },
  { color: 'gold', type: 'phone', age: 7 },
  { color: 'orange', type: 'car', age: 2 },
];

const excludes = [
  { k: 'color', v: 'red' },
  { k: 'color', v: 'blue' },
  { k: 'type', v: 'phone' },
];

function excludeItems(items, excludes) {
  let ref = new Map();
  excludes.forEach((pair) => {
    if (!ref.has(pair.k)) {
      ref.set(pair.k, []);
    }
    ref.get(pair.k).push(pair.v);
  });

  ref.forEach((value, key) => {
    items = items.filter(
      (item) => !value.some((element) => element == item[key]),
    );
  });

  return items;
}

This is the console output (which is correct):

Remaining Items: [
  { color: 'green', type: 'tv', age: 10 },
  { color: 'orange', type: 'car', age: 2 }
]

Answer 1

Although you are using a map for the keys, you're still iterating over all the values in the excludes list -- so the map isn't doing as much work for you as it could be. If, instead, you use composite keys so the key and value are combined into a key in the map, then you can use the efficient map lookup instead of iterating over excludes.

You do still have to iterate over the properties of item, but I assume the number of properties on an item is a constant and is several orders of magnitude smaller than the size of items and excludes? Given m excludes and n items, with p properties on an item, you get O(m+pn), but we've said p is constant so that's O(m+n), provided you're getting O(1) performance from your Map lookup.

const items = [
  { color: 'red', type: 'tv', age: 18 },
  { color: 'silver', type: 'phone', age: 20 },
  { color: 'blue', type: 'car', age: 18 },
  { color: 'green', type: 'tv', age: 10 },
  { color: 'gold', type: 'phone', age: 7 },
  { color: 'orange', type: 'car', age: 2 },
];

const excludes = [
  { k: 'color', v: 'red' },
  { k: 'color', v: 'blue' },
  { k: 'type', v: 'phone' },
];

function excludeItems(items, excludes) {
  let excludesMap = new Map();
  excludes.forEach((pair) => {
    const compositeKey = pair.k + '|' + pair.v;
    excludesMap.set(compositeKey, true);
  });

  return items.filter(item => {
    const doExclude = Object.getOwnPropertyNames(item).some(x => excludesMap.has(x + '|' + item[x]));
    return !doExclude;
  });
}

console.log(excludeItems(items, excludes));

By the way, I chose | as the delimiter between key and value because I assumed that you don't have any properties with | in the key name. If that's not true, you would have to pick a different delimiter.