16
\$\begingroup\$

I need to find the common elements present in all the given arrays. All the arrays are present in another array.

I have come up with this solution and it's working. I tried to remove the usage of indexOf, but I could not. Could someone help me optimize this?

var findCommonElements= function(arrs) {
    var resArr = [];
    for (var i = arrs[0].length - 1; i > 0; i--) {


        for (var j = arrs.length - 1; j > 0; j--) {
            if (arrs[j].indexOf(arrs[0][i]) == -1) {
                break;
            }
        }

        if (j === 0) {
            resArr.push(arrs[0][i]);
        }


    }
    return resArr;
}

Input Array of arrays:

var arrays  = [
    [1, 4, 6, 78, 8, 9, 124, 44],
    [44, 6, 9],
    [124, 44, 16, 9]
]

Output:

findCommonElements( arrays )
[44, 9]
\$\endgroup\$
  • \$\begingroup\$ Are there only ever numbers? \$\endgroup\$ – elclanrs Jul 7 '15 at 15:45
  • \$\begingroup\$ no the numbers can be even and odd \$\endgroup\$ – raj vardhan Jul 7 '15 at 19:28
  • 1
    \$\begingroup\$ I mean can the array only contain numbers, or other data types as well? \$\endgroup\$ – elclanrs Jul 7 '15 at 20:20
  • 1
    \$\begingroup\$ I just tried several different attacks to this, and frankly, I think you've got the fastest thing for the specific purpose. I tested the code samples here, and came up with about 20-30ms runtime (didn't check the one with underscore, since i don't have it, but consider that you have to load underscore to get it, and that takes time...) on 10,000 iterations. Yours is about 5ms. Stylistically, I hate trying to read code with a lot of loops, though. I'd say throw some comments in it for those reading it later, and call it good. :-) \$\endgroup\$ – Eric Blade Jul 15 '15 at 4:42
7
+25
\$\begingroup\$

In your code, you are using arrays to check whether the value is stored. As you have noted, that operation is \$O(n)\$. The solution to this is to use objects to check instead. That operation is \$O(1)\$, meaning that the algorithm goes from \$O(n^2)\$ to \$O(n)\$.

However, there is a problem with storing using objects, namely that all keys need to be strings. Because of this, we have to convert the strings back into integers after we are done.

Hence, our steps become:

  1. Create a currentValues object. Initialize it to contain the values of the first list.
  2. Create a commonValues object, leave it empty.
  3. For each of the arrays, except for the first:
    1. Iterate through the array. If currentValues contains the value, add it to commonValues
    2. Set currentValues = commonValues, and reset commonValues to be an empty object again.
  4. Finally, take the currentValues object, and convert its keys back into integers.

Some code that does the above (I'm no expert with Javascript, while the code works, there may be sub-optimal code here):

var arrays  = [
    [1, 4, 6, 78, 8, 9, 124, 44],
    [44, 6, 9],
    [124, 44, 16, 9]
];
function getCommonElements(arrays){//Assumes that we are dealing with an array of arrays of integers
  var currentValues = {};
  var commonValues = {};
  for (var i = arrays[0].length-1; i >=0; i--){//Iterating backwards for efficiency
    currentValues[arrays[0][i]] = 1; //Doesn't really matter what we set it to
  }
  for (var i = arrays.length-1; i>0; i--){
    var currentArray = arrays[i];
    for (var j = currentArray.length-1; j >=0; j--){
      if (currentArray[j] in currentValues){
        commonValues[currentArray[j]] = 1; //Once again, the `1` doesn't matter
      }
    }
    currentValues = commonValues;
    commonValues = {};
  }
  return Object.keys(currentValues).map(function(value){
    return parseInt(value);
  });
}
console.log(getCommonElements(arrays)); //Prints [9,44]
\$\endgroup\$
  • \$\begingroup\$ your solution is similar to mine however it seems, that for some reason, it takes even more time than op algorithm. Check my v2 of the tests... \$\endgroup\$ – Bruno Costa Jul 15 '15 at 14:20
  • \$\begingroup\$ Bruno, mine has a higher constant in terms of run time because I am creating objects and parsing strings to integers. However, if the arrays were large, this approach would be the fastest. \$\endgroup\$ – Nathan Merrill Jul 15 '15 at 14:42
  • \$\begingroup\$ it doesn't to seem that way. In my tests I generated enough that that your approach would/could win and that didn't happen. \$\endgroup\$ – Bruno Costa Jul 15 '15 at 14:43
  • \$\begingroup\$ I just looked at your approach, and the problem is that it will double count elements. For example, test [[1,1,4,5],[1,4],[4,7,8]]. Your method will return 1 and 4, while mine will return only 4 \$\endgroup\$ – Nathan Merrill Jul 15 '15 at 14:48
  • \$\begingroup\$ there was a problem earlier but there isn't anymore. But I found the issue I'll be fixing it in my jsperf snippet \$\endgroup\$ – Bruno Costa Jul 15 '15 at 15:08
4
\$\begingroup\$

Depending upon the size of your arrays, rather than looping for comparisons I would suggest adding them to a list and sorting to find duplicates. Use the first element of a tuple to enumerate the array if it makes debugging easier.

    [1, 4, 6, 78, 8, 9, 124, 44],
    [44, 6, 9],
    [124, 44, 16, 9]

becomes

    [1, 4, 6, 78, 8, 9, 124, 44 ,44, 6, 9, 124, 44, 16, 9]

becomes

    [1, 4, 6, 6, 8, 9, 9, 9, 16, 44 ,44, 44, 78, 124, 124]

and use a control-break routine to pick the elements having a frequency count of 3 (or whatever).

For larger populations you would do this by tree traversal.

\$\endgroup\$
  • \$\begingroup\$ I like your strategy. If the arrays can contain duplicates, removing those duplicates before concatenation might be a good idea too. E.g. [8, 8, 1], [5, 4, 8], [1, 2, 9] would still have three 8s in the final count, even though 3 is present in only two arrays. \$\endgroup\$ – user27318 Jul 7 '15 at 22:40
  • \$\begingroup\$ Yes, of course, otherwise one must differentiate between the arrays. I can't colourise my answer. ..and the tree traversal really only pays off if these are "keys" for larger records. \$\endgroup\$ – mckenzm Jul 7 '15 at 23:07
  • \$\begingroup\$ But what do you think about time and space complexity if we try this approach \$\endgroup\$ – raj vardhan Jul 8 '15 at 3:35
  • \$\begingroup\$ Providing you have real memory available, it should be comparable. From a coding point of view we would create a new tree instance, an outer loop on the number of arrays, and an inner loop on the elements. Insert into the tree (ignoring duplicates), and traverse the tree. Again if these numbers are key values this is the often the preferred method. If the arrays are small the OP's approach is still valid. \$\endgroup\$ – mckenzm Jul 9 '15 at 3:25
  • \$\begingroup\$ This approach would not take into account when one of the arrays has duplicate entries, would it not? For instance, if the first array has 3 1s, then your algorithm would put that as part of the intersection of the arrays, right? Did I misunderstand? \$\endgroup\$ – Frank Bryce Jul 12 '15 at 17:33
3
\$\begingroup\$

I think you have the optimized solution, I haven't tested the performance factor of this solution, please see whether this solution will work for you.

function findCommonElements(arr) {

    // an array to hold the count of each elements in the input elements
    var lookupArray = [];

    // an array to hold the common elements in all the array
    var commonElementArray = [];

    // iterates through each elements in the array to find the common elements
    for (var arrayIndex = 0; arrayIndex < arr.length; arrayIndex++) {
        for (var childArrayIndex = 0; childArrayIndex < arr[arrayIndex].length; childArrayIndex++) {

            // check whether we have already find the current element
            if (lookupArray[arr[arrayIndex][childArrayIndex]]) {

                // we have already seen this element, so increment count by one
                lookupArray[arr[arrayIndex][childArrayIndex]]++;
            } else {
                // this is a new element so set the count to 1
                lookupArray[arr[arrayIndex][childArrayIndex]] = 1;
            }

            // check the updated count of the current element in the look up table, if the 
            // count is same as the number of input arrays, then its a common element
            if (lookupArray[arr[arrayIndex][childArrayIndex]] == arr.length) {

                // this is a common element, push it to the array
                commonElementArray.push(arr[arrayIndex][childArrayIndex]);
            }
        }
    }

  //  console.log(commonElementArray);
    return commonElementArray;
}

Explainer

Basically we will maintain look up array which is an array of counters. When ever we find a element in the input array we will increment the counter value by 1 which is identified by the index corresponds to the value of element we got from the array.

For ex if you have an array like this [1,5,6] after the iteration the look array would look like this

lookUpArray[0] = undefined;
lookUpArray[1] = 1;
lookUpArray[2] = undefined;
lookUpArray[3] = undefined;
lookUpArray[4] = undefined;
lookUpArray[5] = 1;
lookUpArray[6] = 1;

Subsequent iterations will add or increment the counter values, and we have a common element whenever we have a counter value identified by index corresponds to the element has same value as that of number of input array.

Hope I have made myself clear. Please let me know of your comments

\$\endgroup\$
3
\$\begingroup\$

UPDATE (ORIGINAL POST BELOW):

I just saw this function in the Underscore API, which is the most succinct, yet. If readability is your goal, then consider this option. Also, it seems to be the most performant for all data sets that I've tried.

var arrays  = [
    [1, 4, 6, 78, 8, 9, 124, 44],
    [44, 6, 9],
    [124, 44, 16, 9]
];

console.time('sample 3 length');
var output = findCommonElements(arrays);
console.timeEnd('sample 3 length');
console.log(output); // [9,44]

function findCommonElements(inArrays) {
  // check for valid input
  if (typeof inArrays==="undefined") return undefined;
  if (typeof inArrays[0]==="undefined") return undefined;
  
  return _.intersection.apply(this, inArrays);
}
<script src="http://underscorejs.org/underscore-min.js"></script>

UPDATE: I added timers, and it turns out that although the bottom program has a low "big O" run time, the small input array sample here is not nearly large enough to see the payoff. Also _.intersection() seems to be at least as performant for scaling as well. Further, I've tested this against other solutions here and it seems to be the fastest on this page.

ORIGINAL POST:

I'll add another answer here, which I think is very similar to the answer from @mckenzm but with edge cases taken care of, and a working example.

Before I continue, I'll just point out that Underscore, a favorite library of mine, makes a similar run-time version of your example but with fewer lines of code.

var arrays  = [
    [1, 4, 6, 78, 8, 9, 124, 44],
    [44, 6, 9],
    [124, 44, 16, 9]
];

console.time('sample 1 length');
var output = findCommonElements(arrays);
console.timeEnd('sample 1 length');
console.log(output); // [9,44]

// functions
function findCommonElements(inArrays) {
  // check for valid data
  if (typeof inArrays==="undefined") return undefined;
  if (typeof inArrays[0]==="undefined") return undefined;
  
  // intersect adjacent arrays
  var outArray = inArrays[0];
  _.each(inArrays, function(arr) {
    outArray = intersect(outArray, arr);
  });
  return outArray;
}

function intersect(arr1, arr2) {
  return _.filter(arr1, function(el) {
    return _.contains(arr2, el);
  });
}
<script src="http://underscorejs.org/underscore-min.js"></script>

OK, so that was a more understandable solution, which has a similar run-time efficiency as yours. Now, the following I think will be more scalable.

Strategy:

  1. Get an array without duplicates for each of your input arrays. This ensures that step 4 produces the correct output.

    Output will be:

    var uniqueArrays = [
        [1, 4, 6, 78, 8, 9, 124, 44],
        [44, 6, 9],
        [124, 44, 16, 9]
    ];
    
  2. Concatenate the unique arrays together:

    var concatenatedUniqueArrays = [1, 4, 6, 78, 8, 9, 124, 44, 44, 6, 9, 124, 44, 16, 9];
    
  3. Sort the resulting array:

    var sortedUniqueElements = [1, 4, 6, 6, 8, 9, 9, 9, 16, 44 ,44, 44, 78, 124, 124];
    
  4. Add only the elements to the final answer which appear the same number of times as the total number of input arrays:

    var finalAnswer = [9, 44];
    

Example code:

var arrays  = [
    [1, 4, 6, 78, 8, 9, 124, 44],
    [44, 6, 9],
    [124, 44, 16, 9]
];

console.time('sample 2 length');
var output = findCommonElements(arrays);
console.timeEnd('sample 2 length');
console.log(output); // [9,44]

function findCommonElements(inArrays) {
  // check for valid data
  if (typeof inArrays==="undefined") return undefined;
  if (typeof inArrays[0]==="undefined") return undefined;

  // step 1: Get an array without duplicates for each of your input arrays. 
  var uniqueArrays = [];
  _.each(inArrays, function (arr, i) {
    uniqueArrays[i] = _.uniq(arr);
  });
  console.log("uniqueArrays", uniqueArrays); // same as inArrays... there are no duplicates in each array
  
  // step 2: Concatenate the unique arrays together
  var concatenatedUniqueArrays = [];
  _.each(uniqueArrays, function (arr) {
    concatenatedUniqueArrays = concatenatedUniqueArrays.concat(arr);
  });
  console.log("concatenatedUniqueArrays", concatenatedUniqueArrays); // [1, 4, 6, 78, 8, 9, 124, 44, 44, 6, 9, 124, 44, 16, 9]
  
  // step 3: sort the resulting array
  var sortedUniqueElements = _.sortBy(concatenatedUniqueArrays, function(el) { return el; });
  console.log("sortedUniqueElements", sortedUniqueElements); // [1, 4, 6, 6, 8, 9, 9, 9, 16, 44, 44, 44, 78, 124, 124]
  
  // step 4: add only the elements to the final answer
  //         which appear the same number of times as
  //         the total number of input arrays.
  var finalAnswer = [];
  var prevElement = sortedUniqueElements[0];
  var prevElementCount = 1;
  for (var idx=1; idx < sortedUniqueElements.length; idx++) {
    var currentElement = sortedUniqueElements[idx];
    if (currentElement === prevElement) {
      prevElementCount++;
      if (prevElementCount === inArrays.length) {
        finalAnswer.push(prevElement);
      }
    } else {
      prevElementCount = 1;
    }
    prevElement = currentElement;
  }
  
  return finalAnswer; // [9, 44]
}
<script src="http://underscorejs.org/underscore-min.js"></script>

\$\endgroup\$
1
\$\begingroup\$

How about finding the unique shortest input argument list and filtering out nodes that appear in all remaining input lists?

Something like this:

function findCommonElements ()  {

    return unique( // get unique list of nodes for shortest list argument
      Array.prototype.shift.call(
        Array.prototype.sort.call(
          arguments, 
          function ( ls1, ls2 ) { return ls1.length - ls2.length; })
      )
    ).filter( // filter out those that apear in all remaining input lists
      function ( node ) {
          return Array.prototype.every.call(this, 
            function (ls) { return -1 != ls.indexOf(node); }
          );
      }, 
      arguments
    );
}

where .unique() is @megawc's implementation of .unique().

\$\endgroup\$
0
\$\begingroup\$

I've decided to share my two pence on the matter. It's quite a process but let's see what comes of it:

Testing Environment

First, let me show you how I tested this. I tested with the following code:

function logTime(fn, msg){
    var t = Date.now();
    for(var i = 0; i < 1000; i++){
        fn();
    }
    document.body.innerHTML += msg
    document.body.innerHTML += Date.now() - t;
    document.body.innerHTML += 'ms<br />';
}

Now I know this isn't the most accurate, but I believe both functions have the same disadvantages here, so executing it 1000 times in a row will show the better one.

Larger Sample Creation

Now, I also built a function to give it a bit of a bigger sample input. The small differences are hard to notice any differences with, but my solution is significantly faster when it comes to larger arrays. Heres the function I used to randomly generate a large arrays of arrays:

function compriseArrays(){
    var randAmount = Math.round(Math.random() * 10);
    var result = new Array();
    for(var i = 0; i < randAmount; i++){
        result[i] = new Array();
        var count = 0;
        var randSize = Math.round(Math.random() * 500);
        for(var r = 0; r < randSize; r++){
            var plus = Math.round(Math.random() * 5);
            count += plus;
            result[i][r] = count;
        }
    }
    return result;
}

This only gets ran once, and sometimes creates larger and sometimes smaller arrays, but usually big enough to allow this test to make results obvious.

The Solution

Now my solution is to do a quick loop through the arrays to find the shortest one, significantly cutting down on the potential time we spend analysing every array:

function findCommon(arrays){
    var result = [];
    // First, find the shortest array of them all
    var array = arrays.length-1;
    for(var i = arrays.length-1; i >= 0; i--){
        if(arrays[i].length < arrays[array].length) array = i;
    }
    // Then execute the already existing function
    for(var i = arrays[array].length-1; i >= 0; i--){
        var j = arrays.length-1;
        for(; j > 0; j--){
            if(arrays[j].indexOf(arrays[array][i]) < 0) break;
        }
        if(j == 0) result.push(arrays[array][i]);
    }
    return result;
}

For all intents and purposes, the function is the same as yours, apart from the i >= 0, which made your function ignore the first item in every array, even though it could be a match. Now lets put this to the test:

The Results

function compriseArrays(){
	var randAmount = Math.ceil(Math.random() * 10);
	var result = new Array();
	for(var i = 0; i < randAmount; i++){
		result[i] = new Array();
		var count = 0;
		var randSize = Math.ceil(Math.random() * 500);
		for(var r = 0; r < randSize; r++){
			var plus = Math.ceil(Math.random() * 5);
			count += plus;
			result[i][r] = count;
		}
	}
	return result;
}

// My Function
function findCommon(arrays){
	var result = [];
	var array = arrays.length-1;
	for(var i = array; i > 0; i--){
		if(arrays[i].length < arrays[array].length) array = i;
	}
    for(var i = arrays[array].length-1; i >= 0; i--){
		var j = arrays.length-1;
		for(; j > 0; j--){
			if(arrays[j].indexOf(arrays[array][i]) < 0) break;
		}
		if(j == 0) result.push(arrays[array][i]);
	}
	return result;
}

// OP's Functions
var findCommonElements = function(arrs) {
    var resArr = [];
    for (var i = arrs[0].length - 1; i >= 0; i--) {

        for (var j = arrs.length - 1; j > 0; j--) {
            if (arrs[j].indexOf(arrs[0][i]) == -1) {
                break;
            }
        }

        if (j === 0) {
            resArr.push(arrs[0][i]);
        }

    }
    return resArr;
}

function logTime(fn, msg){
	var t = Date.now();
	for(var i = 0; i < 1000; i++){
		fn();
	}
	document.body.innerHTML += msg
	document.body.innerHTML += Date.now() - t;
	document.body.innerHTML += 'ms<br />';
}

var largeArray = compriseArrays();

var allitems = 0;
for(var i = 0; i < largeArray.length; i++){
for(var j = 0; j < largeArray[i].length; j++){
allitems++;
}
}

var findCommonResult = findCommon(largeArray).join(', ');
var findCommonElementsResult = findCommon(largeArray).join(', ');

logTime(function(){
	findCommon(largeArray);
}, 'findCommon() in Array(length: ' + allitems + ') -> [' + findCommonResult + '] : ');
logTime(function(){
	findCommonElements(largeArray);
}, 'findCommonElements() in Array(length: ' + allitems + ') -> [' + findCommonElementsResult + '] : ');

Note: If the above snippet shows the same amount of time consumed, please run it again, as there is a slight chance that the first array is the shortest array, and therefor both functions would take the same amount of time. If my function is slower, try again as you might have gotten a significantly small random set of arrays back, and I explain below why this could be slower.

Now, this function will usually do better than yours as I am using already defined variables to find the shortest route through this. Only when the arrays you are scanning are really small, or one of the earliest arrays is the shortest, or the amount of arrays is higher than the amount of entries in the first one, does the advantage dissappear, as the loop through the array length may extend the time it takes to execute the function.

\$\endgroup\$

protected by Jamal Dec 24 '18 at 8:11

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.