How to find 'overlapping' values from an array of objects in JavaScript?

Question

Given two arrays of objects, how can I find all objects that contain an 'overlapping' value (e.g. price in this case)?

For example, given array A and array B, how can I find all objects where the "price" is either an exact match (e.g. 20, 30) or contained within this overlap (e.g. 20.45)?

var A = [
  { "id" : 1, "price" : 50, "quantity": 2 },
  { "id" : 2, "price" : 40, "quantity": 2 },
  { "id" : 3, "price" : 30, "quantity": 2 }, // yes
  { "id" : 4, "price" : 20, "quantity": 2 }  // yes
];

var B = [
  { "id" : 5, "price" : 30, "quantity": 2 }, // yes
  { "id" : 6, "price" : 20.45, "quantity": 2 }, // yes
  { "id" : 7, "price" : 20, "quantity": 2 }, // yes
  { "id" : 8, "price" : 10, "quantity": 2 },
  { "id" : 9, "price" : 5, "quantity": 2 }
];


// Goal
var C = [
  { "id" : 3, "price" : 30, "quantity": 2 }, // yes
  { "id" : 4, "price" : 20, "quantity": 2 }  // yes
];
var D = [
  { "id" : 5, "price" : 30, "quantity": 2 }, // yes
  { "id" : 6, "price" : 20.45, "quantity": 2 }, // yes
  { "id" : 7, "price" : 20, "quantity": 2 }, // yes
];

My goal is to keep them separated into their own arrays (C & D). But if the end result needs to be one combined array, that's okay. I can probably make that work too. Anything that works would make me happy right now.

I've tried Underscore's intersection. If A & B were simple arrays containing integers rather than objects, then intersection would work to find the exact matches (e.g. 30 & 30, 20 & 20), but it still wouldn't include 20.45, which I need as well. And, of course, I have an array of objects instead of simple arrays, which makes it a bit harder as well.

simple loop can do this... – monkeyinsight Apr 14 '13 at 19:36 — monkeyinsight, Apr 14 '13 at 19:36

score 0 · Accepted Answer · edited May 23 '17 at 11:57

0

It seems we can assume that those arrays are sorted by price (if not, do so - see Sorting an array of JavaScript objects and similar), and that A contains higher prices than B (if not, you'd need to invert the logic). Then just do:

var i = A.length - 1,
    j = 0,
    overlapMin = A[i].price,
    overlapMax = B[j].price;
while (A[i].price <= overlapMax) i--;
while (B[j].price >= overlapMin) j++;
var C = A.slice(i+1), // to end
    D = B.slice(0, j);

If you need better performance on a really huge set, you could use binary searches for the boundaries i and j as well.

edited May 23 '17 at 11:57

Community

1
1

answered Apr 14 '13 at 21:53

Bergi

630,263
148
957
1,375

That works! And looks very efficient. I am sorting them by price.I tried to click up vote, it wouldn't let me as an SO noob yet, and it came back as a -1. Not sure if that was me or it just updating the tally. Sorry about that if I accidentally did it trying to upvote. ;) WTH Stackoverflow? – inkedd Apr 14 '13 at 22:12

monkeyinsight · Answer 2 · 2013-04-14T20:44:45.613

-1

var C = [], D = [];
for (var i in A)
    for (var j in B)
        if (A[i].price > B[j].price-1 && A[i].price < B[j].price+1) {
             C.push(A[i]);
             D.push(B[j]);
        }

edited Apr 14 '13 at 20:44

answered Apr 14 '13 at 19:41

monkeyinsight

4,719
1
20
28

Hmm Something is slightly off. C & D end up with more objects than A & B. http://jsfiddle.net/R5vjN/ – inkedd Apr 14 '13 at 20:34
yea, there should be && not || – monkeyinsight Apr 14 '13 at 20:44
[Do not use `for-in`-loops with arrays!!!](http://stackoverflow.com/q/500504/1048572) – Bergi Apr 14 '13 at 21:40
That's darn close. Cool. The only problem is that it's adding one of the objects from A twice to C (`{"id":4,"price":20,"quantity":2}`). So I tried removing the objects after they're pushed onto C or D, but that kills the script. http://jsfiddle.net/tU4en/ – inkedd Apr 14 '13 at 21:46
What do those `+1` and `-1` after the prices do there? – Bergi Apr 14 '13 at 21:56

How to find 'overlapping' values from an array of objects in JavaScript?

2 Answers2