Javascript equivalent of php's array_intersect?

Posted on 2006-07-19
Last Modified: 2010-10-05

Let start of by having comma-separated strings with [a-z] words (no other characters):
var string1 = "apple,pear,banana,grape,strawberry";
var string2 = "strawberrry,raspberry,blueberry";

What is the most efficent way to determine which words are in both arrays. (assuming the strings are split on comma's)

regular expressions and split/join are fine ofcourse, but I rather avoid nested loops.

Any thoughs?

Question by:Roonaan
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
LVL 12

Expert Comment

ID: 17138253

var string_1 = "," + string1 + ";";
for (<each item in string2>) if(string_1.indexOf("," + item + ",") != -1) <common item>;
LVL 19

Accepted Solution

dakyd earned 500 total points
ID: 17140080
I'm not sure, but doing an indexOf() on either of the strings seems like it would be roughly equivalent (performance-wise) to doing a full search of the split array.  I can't back it up, but that's just what gut instinct tells me.

Assuming string1 has m elements and string2 has n elements, my idea was to make an algorithm with O(m+n) rather than O(m*n).  So, split the strings, sort the resulting arrays, then do a linear search through the two arrays.  Since they're sorted, you never have to back-track, and each element in arr1 is compared to an element in arr2 once and only once.  Of course, if indexOf() is fast enough, it may not matter at all.  Regardless, hope that helps.

<script type="text/javascript">
var string1 = "apple,pear,banana,grape,strawberry";
var string2 = "strawberry,raspberry,blueberry";

var arr1 = string1.split(",").sort();
var arr2 = string2.split(",").sort();

var common = new Array();
for (var i = 0, n = arr1.length, j = 0, k = arr2.length; (i < n) && (j < k); i ++)
  if (arr1[i] == arr2[j])
    common[common.length] = arr1[i];
    j ++;
  else if (arr1[i] > arr2[j])
    j ++;
    i --;

LVL 12

Expert Comment

ID: 17140111
Your algorithm is faster, but not O(m+n) (because of sorting). Sorting is at best O(m) + O(n).
LVL 49

Author Comment

ID: 17140128
I think I'll go with your code dakyd, with minor adjustment of using common.push(arra1[i]);

Thanks a lot

LVL 19

Expert Comment

ID: 17140312
Oops, you're right, I hadn't thought about the sorting ... regardless, glad it helped.

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Read text on Table 7 49
Validating number not work with decimal 4 46
What kind of script/language created this graph? 6 65
Make icons act like add/minus for qtys 6 43
I've been trying to accomplish this for a while and it just struck me yesterday how to accomplish this task. I have done searches all over the internet looking for ways to email pages from my applications and finally I have done it!!! Every single s…
The task A number given should be formatted for easy reading by separating digits into triads. Format must be made inline via JavaScript, i.e., frameworks / functions are not welcome. So let’s take a number like this “12345678.91¿ and format i…
The viewer will learn the basics of jQuery, including how to invoke it on a web page. Reference your jQuery libraries: (CODE) Include your new external js/jQuery file: (CODE) Write your first lines of code to setup your site for jQuery.: (CODE)
The viewer will learn the basics of jQuery including how to code hide show and toggles. Reference your jQuery libraries: (CODE) Include your new external js/jQuery file: (CODE) Write your first lines of code to setup your site for jQuery…

739 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question