Get common elements from two Arrays in JavaScript

In this tute, we will discuss how to get common elements between two Arrays in JavaScript. Prior to getting into the topic, let’s see what is an array.

An array is a special variable that can contain more than one value. These elements can be of the same or different data types. Few examples of arrays are,

// Arrays of single type of elements
var arr1 = [1, 3, 4];
var arr2 = ['a', '3', 'foo'];
var arr3 = [1.3, 10.45];

// Array with multiple types of elements
var arr4 = [1, 'abc', 55.99];

JavaScript code to get common elements from two Arrays

By ‘get common elements from two arrays’, here we mean the mathematical intersection of two arrays. Those elements which are present in both the arrays are referred to as common elements here.

There are many ways to get the common elements. Let’s see two of them here and their time complexities.

Method 1:

In the first method, we are going to iterate through all the elements of an array and check if it is present in the other array. Following is the algorithm used to get the common elements.

Algorithm:

  1. Firstly, iterate through all the elements in one of the arrays.
  2. Then, for each element in this array, iterate through all the elements of the other array.
  3. If the element is present, then add this element to the new array.
  4. Otherwise, continue with the next element.

Implementation:

// Function to return commonElements
function getCommon(arr1, arr2) {
  var common = [];                   // Array to contain common elements

  for(var i=0 ; i<arr1.length ; ++i) {
    for(var j=0 ; j<arr2.length ; ++j) {
      if(arr1[i] == arr2[j]) {       // If element is in both the arrays
        common.push(arr1[i]);        // Push to common array
      }
    }
  }
  
  return common;                     // Return the common elements
}

var arr1 = [45, 99, 55, 223, 17, 93, 23];
var arr2 = [45, 18, 93, 7, 23, 1, 223, 5];

// Get common elements of arr1, arr2
var commonElements = getCommon(arr1, arr2); // [45, 223, 93, 23]

Time Complexity:

Since we are using nested loops on lengths of both the arrays, the time complexity is O(n2) or O(n*m).

Method 2:

In this method, we are going to sort both the arrays and then find the common elements. This method is more efficient than the previous method because of reduced time complexity. Following is the algorithm used to get the common elements.

Algorithm:

  1. Firstly, sort both the arrays.
  2. Then, Keep a pointer for each of the two arrays.
  3. If both elements that are being pointed are equal, then it is a common element.
  4. Otherwise, increment the pointer of the array with a lower value of the current element.
  5. Stop this until one of the arrays goes out of elements.

Implementation:

// Function to return commonElements
function getCommon(arr1, arr2) {
  arr1.sort();                      // Sort both the arrays
  arr2.sort();
  var common = [];                  // Array to contain common elements

  var i = 0, j = 0;                 // i points to arr1 and j to arr2

  // Break if one of them runs out
  while(i<arr1.length && j<arr2.length) {
  	
    if(arr1[i] == arr2[j]) {        // If both are same, add it to result
      common.push(arr1[i]);
      i++;
      j++;
    }
    else if(arr1[i] < arr2[j]) {  // Increment the smaller value so that
      i++;                        // it could be matched with the larger
    }                             // element
    else {
      j++;
    }
  }
  
  return common;
}

var arr1 = [45, 99, 55, 15, 17, 93, 23];
var arr2 = [45, 18, 93, 7, 23, 1, 15];

// Get common elements of arr1, arr2
var commonElements = getCommon(arr1, arr2); // [15, 23, 45, 93]

Time Complexity:

Since we are sorting the elements and running through the lengths of the arrays, our time complexity would be,

O(nLog2n + mLog2m + n + m) or O(nLog2n + n). Since nLog2n is greater than n, we can say that the time complexity is O(nLog2n).

Finally, If you have any queries or doubts on how to get common elements from two arrays in JavaScript, simply comment in the comment section provided below.

Related posts:

Leave a Reply

Your email address will not be published. Required fields are marked *