# Find Common Elements Between Two Arrays
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-common-elements-between-two-arrays)
Canonical: https://scaleengineer.com/dsa/problems/find-common-elements-between-two-arrays
**Data structures:** Array, Hash Table
---
## Problem
You are given two integer arrays `nums1` and `nums2` of sizes `n` and `m`, respectively. Calculate the following values:

* `answer1` : the number of indices `i` such that `nums1[i]` exists in `nums2`.
* `answer2` : the number of indices `i` such that `nums2[i]` exists in `nums1`.

Return `[answer1,answer2]`.

**Example 1:**

**Input:** nums1 = \[2,3,2\], nums2 = \[1,2\]

**Output:** \[2,1\]

**Explanation:**

![](https://assets.glich.co/dsa/find-common-elements-between-two-arrays/image0.gif)

**Example 2:**

**Input:** nums1 = \[4,3,2,3,1\], nums2 = \[2,2,5,2,3,6\]

**Output:** \[3,4\]

**Explanation:**

The elements at indices 1, 2, and 3 in `nums1` exist in `nums2` as well. So `answer1` is 3.

The elements at indices 0, 1, 3, and 4 in `nums2` exist in `nums1`. So `answer2` is 4.

**Example 3:**

**Input:** nums1 = \[3,4,2,3\], nums2 = \[1,5\]

**Output:** \[0,0\]

**Explanation:**

No numbers are common between `nums1` and `nums2`, so answer is \[0,0\].

**Constraints:**

* `n == nums1.length`
* `m == nums2.length`
* `1 <= n, m <= 100`
* `1 <= nums1[i], nums2[i] <= 100`

# Approaches
## Brute Force using Nested Loops
This approach uses a straightforward, nested-loop method to solve the problem. For each element in the first array, we iterate through the entire second array to check for its existence. We repeat this process for the second array against the first.
**Time:** O(n * m), where `n` is the length of `nums1` and `m` is the length of `nums2`. We have two separate sets of nested loops, one taking O(n * m) and the other O(m * n), resulting in a total time complexity of O(n * m). · **Space:** O(1), as we only use a few variables to store the counts and loop indices. The space for the output array is not considered.
**Pros:** Simple to implement and understand.; Requires minimal extra space (O(1)).
**Cons:** Highly inefficient with a quadratic time complexity, which will be very slow for large arrays.; Likely to result in a 'Time Limit Exceeded' (TLE) error on platforms with stricter time limits for larger inputs.
### Explanation
To find `answer1`, we iterate through each element of `nums1`. For each of these elements, we perform another loop through all elements of `nums2`. If a match is found, we increment `answer1` and break the inner loop to proceed to the next element in `nums1`.

Similarly, to find `answer2`, we iterate through each element of `nums2`. For each element, we loop through `nums1` to find a match. If a match is found, we increment `answer2` and break the inner loop.

This method is simple to understand and implement but is not efficient for large arrays.

```java
class Solution {
    public int[] findIntersectionValues(int[] nums1, int[] nums2) {
        int answer1 = 0;
        int answer2 = 0;

        // Helper function to check if a value exists in an array
        // This could be inlined as well
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                if (num1 == num2) {
                    answer1++;
                    break; // Found a match, move to the next element in nums1
                }
            }
        }

        for (int num2 : nums2) {
            for (int num1 : nums1) {
                if (num2 == num1) {
                    answer2++;
                    break; // Found a match, move to the next element in nums2
                }
            }
        }

        return new int[]{answer1, answer2};
    }
}
```
### Algorithm
- Initialize `answer1` and `answer2` to 0.
- To calculate `answer1`, iterate through each element `num1` in `nums1`.
- For each `num1`, start a nested loop to iterate through each element `num2` in `nums2`.
- If `num1` is equal to `num2`, it means `num1` exists in `nums2`. Increment `answer1` and break the inner loop to avoid multiple counts for the same `num1` and move to the next element in `nums1`.
- To calculate `answer2`, repeat the process. Iterate through each element `num2` in `nums2`.
- For each `num2`, start a nested loop to iterate through each element `num1` in `nums1`.
- If `num2` is equal to `num1`, increment `answer2` and break the inner loop.
- Finally, return the result as `[answer1, answer2]`.

## Using Hash Sets for Efficient Lookups
To improve the time complexity, we can use hash sets. A hash set provides average O(1) time complexity for checking the existence of an element. We can convert the arrays into hash sets to speed up the search process significantly.
**Time:** O(n + m), where `n` is the length of `nums1` and `m` is the length of `nums2`. Populating the sets takes O(n + m), and the two counting loops take O(n) and O(m) respectively. · **Space:** O(n + m), as we need to store the unique elements of both arrays in two separate hash sets. In the worst case, where all elements are unique, the space is proportional to the sum of the lengths of the arrays.
**Pros:** Significantly faster than the brute-force approach with a linear time complexity.; A general-purpose solution that works well even if the range of numbers is large or not constrained.
**Cons:** Uses extra space proportional to the number of unique elements in the arrays.
### Explanation
First, we create two hash sets, `set1` and `set2`, and populate them with the unique elements from `nums1` and `nums2`, respectively. This step takes O(n + m) time.

Then, to calculate `answer1`, we iterate through the original `nums1` array. For each element, we check if it exists in `set2`. Since lookups in a hash set are O(1) on average, this loop takes O(n) time.

Similarly, to calculate `answer2`, we iterate through the original `nums2` array and check for each element's presence in `set1`. This loop takes O(m) time.

The total time complexity is dominated by the linear scans, making it much faster than the brute-force approach.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] findIntersectionValues(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        for (int num : nums1) {
            set1.add(num);
        }

        Set<Integer> set2 = new HashSet<>();
        for (int num : nums2) {
            set2.add(num);
        }

        int answer1 = 0;
        for (int num : nums1) {
            if (set2.contains(num)) {
                answer1++;
            }
        }

        int answer2 = 0;
        for (int num : nums2) {
            if (set1.contains(num)) {
                answer2++;
            }
        }

        return new int[]{answer1, answer2};
    }
}
```
### Algorithm
- Create a `HashSet` named `set1` and add all elements from `nums1` to it.
- Create another `HashSet` named `set2` and add all elements from `nums2` to it.
- Initialize `answer1` to 0.
- Iterate through each element `num` in the original `nums1` array. If `set2` contains `num`, increment `answer1`.
- Initialize `answer2` to 0.
- Iterate through each element `num` in the original `nums2` array. If `set1` contains `num`, increment `answer2`.
- Return the array `[answer1, answer2]`.

## Optimized Approach with Boolean Arrays
Given the constraint that all numbers are between 1 and 100, we can use a highly efficient, constant-space optimization. Instead of a general-purpose hash set, we can use a simple boolean array as a direct-address table to track the presence of numbers.
**Time:** O(n + m), where `n` is the length of `nums1` and `m` is the length of `nums2`. The process involves four separate linear passes: two to populate the boolean arrays and two to count the common elements. · **Space:** O(1), because the size of the boolean arrays (101) is constant and does not depend on the input array sizes `n` and `m`.
**Pros:** Optimal time complexity of O(n + m).; Constant space complexity, making it very memory-efficient.; Often faster in practice than hash sets due to better cache performance and no hashing overhead.
**Cons:** This approach is only applicable because of the specific constraint on the range of values in the input arrays (1 to 100). It would not be feasible for a large or unbounded range of numbers.
### Explanation
We create two boolean arrays, `presentInNums1` and `presentInNums2`, both of size 101 (to cover indices 1 to 100). These arrays will act as our lookup tables.

We iterate through `nums1` and mark the corresponding indices in `presentInNums1` as `true`. For example, if we see the number 5, we set `presentInNums1[5] = true`.

We do the same for `nums2` and `presentInNums2`.

To find `answer1`, we iterate through `nums1` again. For each number `num`, we check `presentInNums2[num]`. If it's `true`, we increment `answer1`.

To find `answer2`, we iterate through `nums2`. For each number `num`, we check `presentInNums1[num]`. If it's `true`, we increment `answer2`.

This approach has the same time complexity as the hash set method but uses constant extra space, making it the most efficient solution for the given constraints.

```java
class Solution {
    public int[] findIntersectionValues(int[] nums1, int[] nums2) {
        boolean[] presentInNums1 = new boolean[101];
        for (int num : nums1) {
            presentInNums1[num] = true;
        }

        boolean[] presentInNums2 = new boolean[101];
        for (int num : nums2) {
            presentInNums2[num] = true;
        }

        int answer1 = 0;
        for (int num : nums1) {
            if (presentInNums2[num]) {
                answer1++;
            }
        }

        int answer2 = 0;
        for (int num : nums2) {
            if (presentInNums1[num]) {
                answer2++;
            }
        }

        return new int[]{answer1, answer2};
    }
}
```
### Algorithm
- Create a boolean array `presentInNums1` of size 101, initialized to `false`.
- Iterate through `nums1`, and for each `num`, set `presentInNums1[num] = true`.
- Create a boolean array `presentInNums2` of size 101, initialized to `false`.
- Iterate through `nums2`, and for each `num`, set `presentInNums2[num] = true`.
- Initialize `answer1` to 0. Iterate through `nums1`, and for each `num`, if `presentInNums2[num]` is `true`, increment `answer1`.
- Initialize `answer2` to 0. Iterate through `nums2`, and for each `num`, if `presentInNums1[num]` is `true`, increment `answer2`.
- Return the array `[answer1, answer2]`.

# Solutions
### Java

```java
class Solution {
public
  int[] findIntersectionValues(int[] nums1, int[] nums2) {
    int[] s1 = new int[101];
    int[] s2 = new int[101];
    for (int x : nums1) {
      s1[x] = 1;
    }
    for (int x : nums2) {
      s2[x] = 1;
    }
    int[] ans = new int[2];
    for (int x : nums1) {
      ans[0] += s2[x];
    }
    for (int x : nums2) {
      ans[1] += s1[x];
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> findIntersectionValues(vector<int> &nums1, vector<int> &nums2) {
    int s1[101]{};
    int s2[101]{};
    for (int &x : nums1) {
      s1[x] = 1;
    }
    for (int &x : nums2) {
      s2[x] = 1;
    }
    vector<int> ans(2);
    for (int &x : nums1) {
      ans[0] += s2[x];
    }
    for (int &x : nums2) {
      ans[1] += s1[x];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findIntersectionValues(self, nums1: List[int], nums2: List[int]) -> List[int]: s1, s2 = set(nums1), set(nums2) return [sum(x in s2 for x in nums1), sum(x in s1 for x in nums2)]

```