Intersection of Two Arrays

Finding the intersection of two arrays is a common coding problem that tests your ability to work with arrays and set operations. The task is simple: you need to find the common elements present in both arrays. This problem often comes up in coding interviews and is a great way to practice your skills in array manipulation and data structures. If you're looking to improve your problem-solving abilities and tackle real-world challenges, knowing how to find the intersection of two arrays is essential. In this lesson, we’ll explore different methods to solve the problem efficiently using techniques like hashing, sorting, and two-pointer approaches.

Steps for Intersection of Two Arrays

• Understand the Problem:
  • You are given two arrays, and the goal is to find the common elements that appear in both arrays.
  • Each element in the arrays may appear multiple times, but you only need to list it once in the result.
• Using Hashing (Set Approach):
  • Create a set from the first array to remove duplicates and store unique elements.
  • Then, iterate through the second array and check if each element exists in the set.
  • Add the common elements to the result.
  • Time Complexity: O(n), Space Complexity: O(n).
• Sorting and Two Pointers Approach:
  • Sort both arrays first.
  • Use two pointers: one for each array. Compare the elements at the current pointers and move the pointers accordingly.
  • If both elements match, add it to the result.
  • Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) for the two-pointer method.
• Edge Case Considerations:
  • Handle arrays of different lengths.
  • Ensure that the arrays may contain duplicate elements, but the result should list each common element only once.
• Optimizing for Performance:
  • For larger datasets, the hashing method is usually the fastest, while the sorting approach can be more memory-efficient.
  • Consider the size and constraints of the problem to choose the best solution.

Have you ever tried to find something in common between two groups of people? Imagine you have two circles of friends. You want to know which friends are in both circles. This is like finding the intersection of two arrays in programming.

Let's think about sports. Consider a basketball player who is great at both offense and defense. The skills needed for each are different, but some players are good at both. These players represent the intersection of offensive and defensive skills – the common elements in two sets of abilities.

In programming, "Intersection of Two Arrays" means finding elements that appear in both arrays. It’s a fundamental problem that helps us compare and connect different sets of data. So, how do we find the intersection of two arrays? Let’s explore this together.

Problem statement

You have two arrays. Your task is to find the elements that are present in both arrays. The result should include only unique elements, even if they appear more than once in both arrays.

Sample input

1array1 = [1, 2, 2, 3, 4]
2array2 = [2, 3, 5, 2]

Sample output

1[2, 3]

Explanation:
In this example, the numbers 2 and 3 appear in both arrays. So, the intersection of the two arrays is [2, 3]. Even though 2 appears multiple times in both arrays, it is only included once in the result.

Brute force approach

Finding the intersection of two arrays might seem simple, but there are different ways to do it, some faster than others. Imagine sorting through two bags of marbles to find matching ones. You could compare each marble in the first bag to every marble in the second bag, but that could take a long time. Instead, you could organize the marbles in both bags, making it easier to find the matching ones.

In programming, we aim to find solutions that are not only correct but also efficient. Let’s look at how we can do that.

Simple idea to start

The simplest way to find the intersection is to compare every element in the first array with every element in the second array. If they match, add the element to the result list, but only if it’s not already there.

Pseudocode

Let’s break down the solution into simple steps that beginners can follow. Here’s the pseudocode in plain English:

• Convert both arrays into sets.
• Find the intersection of the two sets.
• Convert the result back into a list (if needed).
• Return the list of common elements.
• This pseudocode shows a clear way to solve the problem using sets.

Python code

Let’s start with the basic approach, where we manually check each element.

1def intersection_brute_force(array1, array2):
2    result = []
3    for num1 in array1:
4        if num1 in array2 and num1 not in result:
5            result.append(num1)
6    return result

Explanation

• We loop through each element in array1.
• For each element, we check if it’s in array2 and not already in the result list.
• If both conditions are met, we add the element to the result list.

Java code

1import java.util.ArrayList;
2import java.util.List;
3
4public class ArrayIntersection {
5    public static List<Integer> intersectionBruteForce(int[] array1, int[] array2) {
6        List<Integer> result = new ArrayList<>();
7        for (int num1 : array1) {
8            for (int num2 : array2) {
9                if (num1 == num2 && !result.contains(num1)) {
10                    result.add(num1);
11                }
12            }
13        }
14        return result;
15    }
16}

C++ code

1#include <vector>
2#include <algorithm>
3
4std::vector<int> intersectionBruteForce(const std::vector<int>& array1, const std::vector<int>& array2) {
5    std::vector<int> result;
6    for (int num1 : array1) {
7        if (std::find(array2.begin(), array2.end(), num1) != array2.end() && 
8            std::find(result.begin(), result.end(), num1) == result.end()) {
9            result.push_back(num1);
10        }
11    }
12    return result;
13}

Explanation

• The brute force approach compares each element in the first array with every element in the second array.
• If a match is found and it’s not already in the result list, we add it.
• This approach takes longer when the arrays are large because it compares each element many times.

A smarter approach

A more efficient way is to use sets. In Python, sets automatically handle duplicates, which makes them perfect for this problem. By converting both arrays into sets, we can easily find the common elements by intersecting the two sets. This approach is faster and cleaner, especially with large arrays.

Python code

1def intersection_set(array1, array2):
2    set1 = set(array1)
3    set2 = set(array2)
4    return list(set1 & set2)

Explanation

• We convert both arrays into sets using set(array).
• We then find the intersection of the two sets using the & operator.
• The result is converted back to a list.

Java code

1import java.util.HashSet;
2import java.util.Set;
3
4public class ArrayIntersection {
5    public static Integer[] intersectionSet(int[] array1, int[] array2) {
6        Set<Integer> set1 = new HashSet<>();
7        for (int num : array1) {
8            set1.add(num);
9        }
10        Set<Integer> resultSet = new HashSet<>();
11        for (int num : array2) {
12            if (set1.contains(num)) {
13                resultSet.add(num);
14            }
15        }
16        return resultSet.toArray(new Integer[0]);
17    }
18}

C++ code

1#include <unordered_set>
2#include <vector>
3
4std::vector<int> intersectionSet(const std::vector<int>& array1, const std::vector<int>& array2) {
5    std::unordered_set<int> set1(array1.begin(), array1.end());
6    std::vector<int> result;
7    for (int num : array2) {
8        if (set1.find(num) != set1.end()) {
9            if (std::find(result.begin(), result.end(), num) == result.end()) {
10                result.push_back(num);
11            }
12        }
13    }
14    return result;
15}

Explanation

• We use HashSet or unordered_set to store the unique elements of the first array.
• We then go through the second array to find common elements.
• This method is much faster, especially for large arrays.

Conclusion

Finding the intersection of two arrays is like finding common ground between two different groups. The brute force approach is simple but slow. Using sets is a smarter way to solve the problem quickly.

Whether you're comparing small or large datasets, understanding how to find common elements is essential in programming. Remember, finding common ground is key in many aspects of life, not just in programming.