Refrain JavaScript - sift through an array of objects based on the values of a primitive array in linear time

Question

Refrain JavaScript - sift through an array of objects based on the values of a primitive array in linear time

I've got an array of objects that looks like this:

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

My goal is to efficiently filter it (with a time complexity of O(n)) using a simple array like this:

[ '111', '333' ]

The end result should be an array of objects that looks like this:

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

I initially considered using underscoreJS, but there doesn't seem to be a built-in function for this specific task. Any other suggestions?

javascript arrays underscore.js time-complexity

Answer 1

Answer №1

To achieve a solution with linear complexity, it is necessary to make a tradeoff in space complexity in order to perform a single linear search through the array. One approach is to convert the array of matches into a set, reducing the id existence lookup from O(ids.length) to O(1), thereby decreasing the total complexity from O(arr.length*ids.length) to O(arr.length) + O(ids.length):

If there is no room for any space tradeoffs, the total complexity will be quadratic: O(arr.length * ids.length).

ES6 implementation 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 implementation 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) {
  var s = ids.reduce(function(s, id) {
    s[id] = true;
    return s;
  }, Object.create(null));

  return arr.filter(function(item) {
    return s[item.itemId];
  });
}

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

Answer 2

To achieve a solution with linear complexity, it is necessary to make a tradeoff in space complexity in order to perform a single linear search through the array. One approach is to convert the array of matches into a set, reducing the id existence lookup from O(ids.length) to O(1), thereby decreasing the total complexity from O(arr.length*ids.length) to O(arr.length) + O(ids.length):

If there is no room for any space tradeoffs, the total complexity will be quadratic: O(arr.length * ids.length).

ES6 implementation 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 implementation 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) {
  var s = ids.reduce(function(s, id) {
    s[id] = true;
    return s;
  }, Object.create(null));

  return arr.filter(function(item) {
    return s[item.itemId];
  });
}

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

Answer 3

Answer №2

Let's start by assuming

let x = [{
    type: 'glass',
    id: '456'
},
 {
    type: 'glass',
    id: '789'
},
{
    type: 'glass',
    id: '012'
}]

AND

let y = [ '456', '012' ]

Therefore, with the help of underscore methods, we can easily achieve this:

_.filter(x, function(item) {
    return !_.contains(y, item.id)
})

Answer 4

Let's start by assuming

let x = [{
    type: 'glass',
    id: '456'
},
 {
    type: 'glass',
    id: '789'
},
{
    type: 'glass',
    id: '012'
}]

AND

let y = [ '456', '012' ]

Therefore, with the help of underscore methods, we can easily achieve this:

_.filter(x, function(item) {
    return !_.contains(y, item.id)
})

Answer 5

Answer №3

Utilizing a Set to create a blacklist enables us to eliminate duplicates and enhance lookup efficiency.

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

The code above demonstrates that filtered consists of objects from the items array whose itemId is not present in the blacklist.

Answer 6

Utilizing a Set to create a blacklist enables us to eliminate duplicates and enhance lookup efficiency.

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

The code above demonstrates that filtered consists of objects from the items array whose itemId is not present in the blacklist.

Refrain JavaScript - sift through an array of objects based on the values of a primitive array in linear time

Answer №1

Answer №2

Answer №3

Similar questions

I am interested in utilizing a variable's value as an ID within a jQuery function

Tips for extracting the chosen value from a dropdown list within a table cell using JavaScript

Dawn Break Alarm Timepiece - Online Platform

Interactive element for initiating a HTTP request to NodeJS/Express server to trigger a specific function

Issue with sync-request when using post data doesn't seem to be functioning

Sorry, but we couldn't complete your request: User verification unsuccessful: email must be provided

Connecting a specific URL of an API to a single mobile app: A step-by-step guide

How can I make the columns in Next.js / Tailwind expand horizontally first instead of vertically?

Placeholder fails to appear

Is nesting directives possible within AngularJS?

Angular constantly looping due to $watchCollection being triggered repeatedly

Using the Node.js mongodb-native library to insert multiple strings as separate documents

Struggling to navigate the DOM using JavaScript and looking for guidance?

The width of the plotbands on the yAxis of a stacked bar graph is adjusting as the series are dynamically toggled,

Check the input in the text box against the selected options to validate it

Encountered an issue while building npm: "Error: Unable to locate module @restart/context

Connecting Vue.JS page to my existing HTML page: A step-by-step guide

prior to activating a state in angular.js, navigate to a distinct controller

To retrieve the first td element by clicking a button within the corresponding row using JQuery

What is the best way to save a JavaScript variable in local storage?