Javascript equivalent to LEFT OUTER JOIN with NULL in WHERE clause

Question

I have a couple of JS objects like these:

var formulas = [
    {formulaID: 1, lastManufactureDate: '2020-03-24'},
    {formulaID: 3, lastManufactureDate: '2020-03-20'},
    {formulaID: 7, lastManufactureDate: '2020-03-16'},
    {formulaID: 9, lastManufactureDate: '2020-03-20'}
];

var allFormulas = [
    {formulaID: 1, formulaName: 'Chocolate Milk 2%'},
    {formulaID: 2, formulaName: 'Chocolate Milk 1%'},
    {formulaID: 3, formulaName: 'Vanilla Creamer'},
    {formulaID: 4, formulaName: 'Hazelnut Creamer'},
    {formulaID: 5, formulaName: 'Plain Creamer'},
    {formulaID: 6, formulaName: 'White Milk 2%'}
];

I need to find a way to identify all the objects in the formulas array which have formulaIDs that do not exist in the allFormulas array. Basically, the equivalent of doing a LEFT OUTER JOIN with a WHERE clause to find NULLs on the right hand side. In the sample data here, the expected output would be
[{formulaID: 7, lastManufactureDate: '2020-03-16'}, {formulaID: 9, lastManufactureDate: '2020-03-20'}]

In the app the number of objects in the formulas array is about 135 and in the allFormulas array there are around 1,100.

The goal is to do this efficiently and without a third party library. I found a similar question here but it didn't address identifying the objects in one array that aren't in the other. Unfortunately, I don't really know where to start to solve this problem.

Write either a simple [nested loop join](https://en.wikipedia.org/wiki/Nested_loop_join) or a more efficient [hash join](https://en.wikipedia.org/wiki/Hash_join) — Bergi, Mar 24 '20 at 21:16
You can build a map of allFormulas (like authorMap in the link you specify), then use Array.filter to remove formulas that have a match. See the Filtering Out Small Values example in https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/filter — KenOn10, Mar 24 '20 at 21:21

jods · Accepted Answer · 2020-03-24T22:14:26.910

1

Build a set with allFormulas ids, then filter the first array.

var ids = new Set(allFormulas.map(f => f.formulaID));
var result = formulas.filter(f => !ids.has(f.formulaID));

This is O(N+M) in complexity (one iteration of each array, looking up a set should be O(1)). The solution based on nested loops (using a linear search, e.g. find) is O(N*M) which is far worse for large arrays.

edited Mar 24 '20 at 22:14

answered Mar 24 '20 at 22:08

jods

4,581
16
20

score 0 · Answer 2 · answered Mar 24 '20 at 22:03

var formulas = [{
    formulaID: 1,
    lastManufactureDate: '2020-03-24'
  },
  {
    formulaID: 3,
    lastManufactureDate: '2020-03-20'
  },
  {
    formulaID: 7,
    lastManufactureDate: '2020-03-16'
  },
  {
    formulaID: 9,
    lastManufactureDate: '2020-03-20'
  }
];

var allFormulas = [{
    formulaID: 1,
    formulaName: 'Chocolate Milk 2%'
  },
  {
    formulaID: 2,
    formulaName: 'Chocolate Milk 1%'
  },
  {
    formulaID: 3,
    formulaName: 'Vanilla Creamer'
  },
  {
    formulaID: 4,
    formulaName: 'Hazelnut Creamer'
  },
  {
    formulaID: 5,
    formulaName: 'Plain Creamer'
  },
  {
    formulaID: 6,
    formulaName: 'White Milk 2%'
  }
];

let preResult = formulas.map((f) => {
  if (!allFormulas.find((x) => x.formulaID == f.formulaID)) {
    return f
  }
});
let result = preResult.filter(function(el) {
  return el != null;
});
console.log(result);

As we are trying to identify items present in formulas array but not in allFormulas, we map through formulas and check if that object id is present in allFormulas using find method. During this process as we are using map, it returns undefined for the matched items (as we are returning only unmatched ones). To filter out those undefined in preResults object we made use of a filter.

Hope this helps!

Javascript equivalent to LEFT OUTER JOIN with NULL in WHERE clause

2 Answers2