Reduce complexity O^2 of comparison between list of objects

Question

I have two list of objects:

list1 = [{value: 'X'}, {value: 'Y'}, ..., {value: 'Z'}];
list2 = [{value: 'A'}, {value: 'B'}, ..., {value: 'C'}];

I have this code that checks whether the values in list2 are in list1. If it is the code doesn't do anything, if not it should add to list1 (this will create a new list, list3). Which means I'm doing a union between the two list without keeping the repeated values.

for (let i = list2.length-1; i >= 0; i--) {
  let item = list2[i];
  let shared = false;
  for (let j = list1.length-1; j >=0; j--) {
    let childItem = list1[j];
    if (item.value === childItem.value) {
      shared = true;
      break;
    }
  }
  if (!shared) { newValues.push(item); }
}
list3 = list1.concat(newValues);

This works fine, but I was wondering if I could improve this O(n*m).

I'm not sure if the lists are always sorted by default, but from what I've seen both (list1 and list2) are always sorted by value.

Example:

var list1 = [{value: 'bar'}, {value: 'baz'}, {value: 'foo'}, {value: 'foz'}];
var list2 = [{value: 'bar'}, {value: 'foo'}, {value: 'test'}, {value: 'testz'}];
var list3 = union(list1, list2);
list3 = [{value: 'bar'}, {value: 'baz'}, {value: 'foo'}, {value: 'foz'}, {value: 'test'}, {value: 'testz'}];

When you say "whether the values in list2 are in list1" do you mean, if any, or if all, values? — Travis J
– Travis J, Commented Oct 11, 2017 at 19:38

Ori Drori · Accepted Answer · 2017-10-11 19:40:51Z

3

Create a set of the values of list1, and Filter list2 by the values in the set before concating it to list1:

var list1 = [{value: 'bar'}, {value: 'baz'}, {value: 'foo'}, {value: 'foz'}];
var list2 = [{value: 'bar'}, {value: 'foo'}, {value: 'test'}, {value: 'testz'}];

const union = (list1, list2) => list1.concat(
  list2.filter(function({ value }) { // filter list2
    return !this.has(value); // filter out items which value is in the set
  }, new Set(list1.map(({ value }) => value))) // the set of list1 values
);

const list3 = union(list1, list2);

console.log(list3);

answered Oct 11, 2017 at 19:40

Ori Drori

196k32 gold badges243 silver badges233 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Ingo Bürk Over a year ago

The question was about improving the (worst case) complexity. How does your solution do in this regard and is it actually better in terms of asymptotic behavior?

renno Over a year ago

So what is the improvement of your code compared to the one I posted? Is it because you don't create a temp list?

Ori Drori Over a year ago

It's because I don't have a loop inside a loop, which gives you the O(n * m). Creating a Set is O(2n). Filtering list2 is O(m). Concating is O(n + m). So the overall complexity is O(3n + 2m), and we can remove the constants for O(n + m).

Nina Scholz · Accepted Answer · 2017-10-11 19:48:24Z

2

You could use a single loop and store the value in a set for later check. Complexity: O(n).

var list1 = [{ value: 'X' }, { value: 'Y' }, { value: 'C' }, { value: 'Z' }],
    list2 = [{ value: 'A' }, { value: 'B' }, { value: 'C' }, { value: 'D' }],
    list3 = list1
        .concat(list2)
        .filter((s => ({ value }) => !s.has(value) && s.add(value))(new Set));

console.log(list3);

.as-console-wrapper { max-height: 100% !important; top: 0; }

answered Oct 11, 2017 at 19:48

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

2 Comments

Ori Drori Over a year ago

Actually O(n + m) because you iterate list1 + list2

Nina Scholz Over a year ago

@OriDrori, for linear complexity, O(n) is sufficient to describe it.

Collectives™ on Stack Overflow

Reduce complexity O^2 of comparison between list of objects

2 Answers 2

3 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related