CODEWITHSUNDEEP
javascriptarraysalgorithm
Anthony
Anthony

Reputation: 47

Intersect multiple arrays of objects

So first of all, I am not expecting a specific solution to my problem, but instead some insights from more experienced developers that could enlighten me and put me on the right track. As I am not yet experienced enough in algorithms and data structures and I take this as a challenge for myself.

I have n number of arrays, where n >= 2. They all contain objects and in the end, I want an array that contains only the common elements between all these arrays.

array1 = [{ id: 1 }, { id: 2 }, { id: 6 }, { id: 10 }]
array2 = [{ id: 2 }, { id: 4 }, { id: 10 }]
array3 = [{ id: 2 }, { id: 3 }, { id: 10 }]

arrayOfArrays = [array1, array2, array3]

intersect = [{ id: 2 }, { id: 10 }]

How would one approach this problem? I have read solutions using Divide And Conquer, or Hash tables, and even using the lodash library but I would like to implement my own solution for once and not rely on anything external, and at the same time practice algorithms.

Upvotes: 0

Views: 871

Answers (3)

Bergi
Bergi

Reputation: 664767

The general solution is to iterate through an input and check for each value whether it exists in all of the other inputs. (Time complexity: O(l * n * l) where n is number of arrays and l is the average length of an array)

Following the ideas of the other two answers, we can improve this brute-force approach a bit by

  • iterating through the smallest input
  • using a Set for efficient lookup of ids instead of iteration

so it becomes (with O(l * n + min_l * n) = O(n * l))

const arrayOfIdSets = arrayOfArrays.map(arr =>
  new Set(arr.map(val => val.id))
);
const smallestArray = arrayOfArrays.reduce((smallest, arr) =>
  smallest.length < arr.length ? smallest : arr
);
const intersection = smallestArray.filter(val =>
  arrayOfIdSets.every(set => set.has(val.id))
);

Upvotes: 2

Todd Skelton
Todd Skelton

Reputation: 7239

For efficiency, I would start by locating the shortest array. This should be the one you work with. You can run a reduce on the arrayOfArrays to iterate through and return the index of the shortest length.

const shortestIndex = arrayOfArrays.reduce((accumulator, currentArray, currentIndex) => currentArray.length < arrayOfArrays[index] ? currentIndex : accumulator, 0);

Take the shortest array and call the reduce function again, this will iterate through the array and allow you to accumulate a final value. The second parameter is the starting value, which is a new array.

shortestArray.reduce((accumulator, currentObject) => /*TODO*/, [])

For the code, we basically need to loop through the remaining arrays and make sure it exists in all of them. You can use the every function since it will fail fast meaning the first array it doesn't exist in will trigger it to return false.

Inside the every you can call some to check if there is at least one match.

isMatch = remainingArrays.every(array => array.some(object => object.id === currentObject.id))

If it's a match, add it to the accumulator which will be your final result. Otherwise, just return the accumulator.

return isMatch ? [...accumulator, currentObject] : accumulator;

Putting all that together should get you a decent solution. I'm sure there are more optimizations that could be made, but that's where I would start.

reduce

every

some

Upvotes: 2

Alex K
Alex K

Reputation: 8338

A good way to approach these kinds of problems, both in interviews and in just regular life, is to think of the most obvious approach you can come up with, no matter how inefficient, and think think about how you can improve it. This is usually called a "brute force" approach.

So for this problem, perhaps an obvious but inefficient approach would be to iterate through every item in array1 and check if it is in both array2 and array 3, and note it down (in another array) if it is. Then repeat again for each item in array2 and in array 3, making sure to only note down items you haven't noted down before.

We can see that will be inefficient because we'll be looking for a single item in an array many times, which is quite slow for an array. But it'll work!

Now we can get to work improving our solution. One thing to notice is that finding the intersection of 3 arrays is the same as finding the intersection of the third array with the intersection of the first and second array. So we can look for a solution to the simpler problem of the intersection of 2 arrays, to build one of an intersection for 3 arrays.

This is where it's handy to know your datastructures. You want to be able to ask the question, "does this structure contain a particular element?" as quickly as possible. Think about what structures are good for that kind of a lookup (known as search). More experienced engineers have this memorized/learned, but you can reference something like https://www.bigocheatsheet.com/ to see that sets are good at this.

I'll stop there to not give the full solution, but once you've seen that sets are fast at both insertion and search, think about how you can use that to solve your problem.

Upvotes: 1

Related Questions