Cfrtjryk

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]

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.

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

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>

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().

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.

var arrays = [

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

    [44, 6, 9],

    [124, 44, 16, 9]







    var arrays = [

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

        [44, 6, 9],

        [124, 44, 16, 9]

    ]

    function commonValue (...arr) {

        let res = arr[0].filter(function (x) {

            return arr.every((y) => y.includes(x))

        })

        return res;

    }

    commonValue(...arrays);