# 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

1. Initialize an empty array to store the common elements.
2. 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.
3. 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]

### 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

1. Initialize an empty array to store the common elements.
2. Create a hash table (dictionary or map) to store the elements and their corresponding boolean flags.
3. 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.
4. Iterate through the second array and check if each element is present in the hash table
5. 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
6. 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)

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