Find Common Elements Between Two Arrays

EASY

Description

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:

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

Checkout 3 different approaches to solve Find Common Elements Between Two Arrays. Click on different approaches to view the approach and algorithm in detail.

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.

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].

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.

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};
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find Common Elements Between Two Arrays. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Find Common Elements Between Two Arrays

Data Structures:

ArrayHash Table

Find Common Elements Between Two Arrays

Description

Approaches

Using Hash Sets for Efficient Lookups

Algorithm

Complexity Analysis

Pros and Cons

Code Solutions

Video Solution

Similar Questions

Data Structures:

On this page

Subscribe to Scale Engineer newsletter