Finding Common Elements (intersection) between two arrays

Intersection of two arrays, or finding common elements between two arrays involves identifying all unique elements that are present in both the given arrays.

This operation is relevant because it allows you to identify similarities and intersections between datasets. By finding the common elements, you can understand the overlap or shared information between two collections of data. This can be useful in various scenarios, such as comparing customer preferences, identifying common interests among users, or detecting similarities in research findings etc.

Brute Force Approach

The brute force approach to find the common elements between two arrays is a straightforward and simple method. The idea is to compare each element of one array with every element of the other array and check if they are the same. If a match is found, the common element is added to the result set if it is not already added.

Algorithm

Initialize an empty array to store the common elements.
Iterate through the first array.
- For each element in the first array, iterate through the second array.
- Check if the current element from the first array is present in the second array.
- If a match is found, add the the current element to the common elements array if it is not already added.
Return the result array containing all the unique common elements.

Code


# Function to get the common elements between two arrays
def get_common_elements(array1, array2):
  # Initialize an empty array to store the common elements
  common_elements = []

  # Iterate through the first array
  for element in array1:
    # Iterate through the second array
    for item in array2:
      # Check if the current element from the first array is present in the second array
      if element == item:
        # If a match is found, add the element to the common elements array if it is not already added
        if element not in common_elements:
          common_elements.append(element)

  # Return the result array containing all the unique common elements
  return common_elements

# Test the function with sample arrays
array1 = [3, 1, 5, 4, 2, 5]
array2 = [8, 4, 5, 7, 4, 6]
common_elements = get_common_elements(array1, array2)
print(common_elements)  # Output: [5, 4]


#include <iostream>
#include <vector>
#include <algorithm>

// Function to get the common elements between two arrays
std::vector<int> get_common_elements(std::vector<int> array1, std::vector<int> array2) {
  // Initialize an empty vector to store the common elements
  std::vector<int> common_elements;

  // Iterate through the first array
  for (int element : array1) {
    // Iterate through the second array
    for (int item : array2) {
      // Check if the current element from the first array is present in the second array
      if (element == item) {
        // If a match is found, add the element to the common elements vector if it is not already added
        if (std::find(common_elements.begin(), common_elements.end(), element) == common_elements.end()) {
          common_elements.push_back(element);
        }
      }
    }
  }

  // Return the result vector containing all the unique common elements
  return common_elements;
}

int main() {
  // Test the function with sample arrays
  std::vector<int> array1 = {3, 1, 5, 4, 2, 5};
  std::vector<int> array2 = {8, 4, 5, 7, 4, 6};
  std::vector<int> common_elements = get_common_elements(array1, array2);

  // Print the common elements
  for (int element : common_elements) {
    std::cout << element << " ";
  }
  std::cout << std::endl; // Output: 5 4

  return 0;
}


// Function to get the common elements between two arrays
function get_common_elements(array1, array2) {
  // Initialize an empty array to store the common elements
  let common_elements = [];

  // Iterate through the first array
  for (let element of array1) {
    // Iterate through the second array
    for (let item of array2) {
      // Check if the current element from the first array is present in the second array
      if (element === item) {
        // If a match is found, add the element to the common elements array if it is not already added
        if (!common_elements.includes(element)) {
          common_elements.push(element);
        }
      }
    }
  }

  // Return the result array containing all the unique common elements
  return common_elements;
}

// Test the function with sample arrays
let array1 = [3, 1, 5, 4, 2, 5];
let array2 = [8, 4, 5, 7, 4, 6];
let common_elements = get_common_elements(array1, array2);
console.log(common_elements); // Output: [5, 4]


import java.util.ArrayList;
import java.util.List;

public class Main {
  // Function to get the common elements between two arrays
  public static List<Integer> getCommonElements(int[] array1, int[] array2) {
    // Initialize an empty list to store the common elements
    List<Integer> commonElements = new ArrayList<>();

    // Iterate through the first array
    for (int element : array1) {
      // Iterate through the second array
      for (int item : array2) {
        // Check if the current element from the first array is present in the second array
        if (element == item) {
          // If a match is found, add the element to the common elements list if it is not already added
          if (!commonElements.contains(element)) {
            commonElements.add(element);
          }
        }
      }
    }

    // Return the result list containing all the unique common elements
    return commonElements;
  }

  public static void main(String[] args) {
    // Test the function with sample arrays
    int[] array1 = {3, 1, 5, 4, 2, 5};
    int[] array2 = {8, 4, 5, 7, 4, 6};
    List<Integer> commonElements = getCommonElements(array1, array2);
    System.out.println(commonElements); // Output: [5, 4]
  }
}

Time Complexity:

In total, the algorithm involves 3 loops: One loop for iterating through all numbers in the first list. Another loop to iterate through all numbers in the second list and check if any matching element exists. The final loop iterates through all elements in the result array and adds the element to it if it is not already added. The time complexity of this brute force approach is O(N^3) because of 3 loops nested within each other.

Space Complexity:

Other than the result array, we use constant extra space. So the space complexity of this approach would be O(1).

The brute force approach is simple to implement, but it may not be efficient for large arrays, as the time complexity grows quadratically with the size of the input arrays. For larger arrays, it is recommended to use more efficient algorithms, such as sorting or using a hash table, to find the common elements between two arrays.

Optimized Approach using Hashing

This approach uses hash tables which results in much better time complexity.

Algorithm

Initialize an empty array to store the common elements.
Create a hash table (dictionary or map) to store the elements and their corresponding boolean flags.
Iterate through the first array and add each element to the hash table, setting the boolean flag to false. Here false indicates that the current element is not added to the result array yet in case if it exists in the second list.
Iterate through the second array and check if each element is present in the hash table
If the element present and the corresponding boolean flag to false, add the current element to result array and set the boolean flag to true
Return the result array containing all the unique common elements.

Code


# Function to get the common elements between two arrays
def get_common_elements(array1, array2):
  # Initialize an empty array to store the common elements
  common_elements = []

  # Initialize an empty hash table
  hash_table = {}

  # Iterate through the first array
  for element in array1:
    # Add the element to the hash table if not already added, and set the boolean flag to false
    if element not in hash_table:
      hash_table[element] = False

  # Iterate through the second array
  for element in array2:
    # Check if the element exists in the hash table
    if element in hash_table:
      # If it does, and the value in hash table is false,
      if hash_table[element] == False:
        # Add the value to common_elements array
        common_elements.append(element)
        # Set the value in hash table to true
        # which indicates that this element is already added to the common_elements array
        hash_table[element] = True

  # Return the common_elements array
  return common_elements

# Test the function
array1 = [3, 1, 5, 4, 2, 5]
array2 = [8, 4, 5, 7, 4, 6]
common_elements = get_common_elements(array1, array2)
print(common_elements)


#include <iostream>
#include <vector>
#include <unordered_map>

// Function to get the common elements between two arrays
std::vector<int> get_common_elements(std::vector<int>& array1, std::vector<int>& array2) {
  // Initialize an empty array to store the common elements
  std::vector<int> common_elements;

  // Initialize an empty hash table
  std::unordered_map<int, bool> hash_table;

  // Iterate through the first array
  for (int element : array1) {
    // Add the element to the hash table if not already added, and set the boolean flag to false
    if (hash_table.find(element) == hash_table.end()) {
      hash_table[element] = false;
    }
  }

  // Iterate through the second array
  for (int element : array2) {
    // Check if the element exists in the hash table
    if (hash_table.find(element) != hash_table.end()) {
      // If it does, and the value in hash table is false,
      if (!hash_table[element]) {
        // Add the value to common_elements array
        common_elements.push_back(element);
        // Set the value in hash table to true
        // which indicates that this element is already added to the common_elements array
        hash_table[element] = true;
      }
    }
  }

  // Return the common_elements array
  return common_elements;
}

int main() {
  // Test the function
  std::vector<int> array1 = {3, 1, 5, 4, 2, 5};
  std::vector<int> array2 = {8, 4, 5, 7, 4, 6};
  std::vector<int> common_elements = get_common_elements(array1, array2);

  // Print the common elements
  for (int element : common_elements) {
    std::cout << element << " ";
  }
  std::cout << std::endl;

  return 0;
}


// Function to get the common elements between two arrays
function get_common_elements(array1, array2) {
  // Initialize an empty array to store the common elements
  let common_elements = [];

  // Initialize an empty hash table
  let hash_table = {};

  // Iterate through the first array
  for (let element of array1) {
    // Add the element to the hash table if not already added, and set the boolean flag to false
    if (!(element in hash_table)) {
      hash_table[element] = false;
    }
  }

  // Iterate through the second array
  for (let element of array2) {
    // Check if the element exists in the hash table
    if (element in hash_table) {
      // If it does, and the value in hash table is false,
      if (hash_table[element] === false) {
        // Add the value to common_elements array
        common_elements.push(element);
        // Set the value in hash table to true
        // which indicates that this element is already added to the common_elements array
        hash_table[element] = true;
      }
    }
  }

  // Return the common_elements array
  return common_elements;
}

// Test the function
let array1 = [3, 1, 5, 4, 2, 5];
let array2 = [8, 4, 5, 7, 4, 6];
let common_elements = get_common_elements(array1, array2);
console.log(common_elements);


import java.util.ArrayList;
import java.util.HashMap;

public class Main {
  // Function to get the common elements between two arrays
  public static ArrayList<Integer> getCommonElements(int[] array1, int[] array2) {
    // Initialize an empty array list to store the common elements
    ArrayList<Integer> commonElements = new ArrayList<>();

    // Initialize an empty hash map
    HashMap<Integer, Boolean> hashTable = new HashMap<>();

    // Iterate through the first array
    for (int element : array1) {
      // Add the element to the hash table if not already added, and set the boolean flag to false
      if (!hashTable.containsKey(element)) {
        hashTable.put(element, false);
      }
    }

    // Iterate through the second array
    for (int element : array2) {
      // Check if the element exists in the hash table
      if (hashTable.containsKey(element)) {
        // If it does, and the value in hash table is false,
        if (!hashTable.get(element)) {
          // Add the value to commonElements array
          commonElements.add(element);
          // Set the value in hash table to true
          // which indicates that this element is already added to the commonElements array
          hashTable.put(element, true);
        }
      }
    }

    // Return the commonElements array list
    return commonElements;
  }

  public static void main(String[] args) {
    // Test the function
    int[] array1 = {3, 1, 5, 4, 2, 5};
    int[] array2 = {8, 4, 5, 7, 4, 6};
    ArrayList<Integer> commonElements = getCommonElements(array1, array2);
    System.out.println(commonElements);
  }
}

Time Complexity

The time complexity of this approach is O(N + M), where N and M are the lengths of the two input arrays, respectively. The first iteration through the first array takes O(N) time to add the elements to the hash table. The second iteration through the second array takes O(M) time to check if each element exists in the hash table.

Space Complexity

The space complexity of this approach is O(N), where N is the length of the total entries which can be stored by hash table used.

This approach is optimized because it uses a hash table to efficiently store and look up the elements, which allows for constant-time access to the elements. The time complexity is linear, which is better than the quadratic time complexity of the brute-force approach (where you compare each element of the first array with each element of the second array).