Intersection of Two Arrays

Updated on 06 June, 2025
Intersection of Two Arrays header image

Problem Statement

In this problem, you are provided with two integer arrays, nums1 and nums2. Your task is to find out the elements that are present in both arrays, ensuring that each element in the resultant array is unique. This result does not require any specific order, meaning that as long as all the unique common elements are included, the sequence in which they appear does not matter.

Examples

Example 1

Input:

nums1 = [1,2,2,1], nums2 = [2,2]

Output:

[2]

Example 2

Input:

nums1 = [4,9,5], nums2 = [9,4,9,8,4]

Output:

[9,4]

Explanation:

[4,9] is also accepted.

Constraints

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

Approach and Intuition

The problem of finding the intersection of two sets is quite common in data processing. The goal is to determine which items are shared between nums1 and nums2 while ignoring duplicates within the intersection.

  • First, convert both nums1 and nums2 into sets. This transformation automatically removes duplicates from each list and permits operations that are optimal for set interactions.
  • Then, use the intersection method available for sets. This method efficiently finds common elements between the two sets.
  • The resultant set from the intersection operation can then be converted back into a list to satisfy the requirement of returning an array.
  • The function signature involves simply returning this resultant list as the solution.

This approach is efficient due to the properties of sets in Python, which offer average-time complexity for insertion, deletion, and membership tests. Thus, the operations of converting lists to sets and finding their intersection are performed swiftly, which is ideal given the problem constraints.

Solutions

  • Java
java
class Solution {
    public int[] findIntersection(int[] array1, int[] array2) {

        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> tempResult = new ArrayList<>();

        for (int num : array1) {
            map.put(num, 1);
        }

        for (int num : array2) {
            if (map.containsKey(num) && map.get(num) == 1) {
                tempResult.add(num);
                map.put(num, 0);
            }
        }

        return tempResult.stream().mapToInt(i -> i).toArray();
    }
}

The provided Java solution tackles the problem of finding the intersection of two arrays. In this implementation, two arrays are given as input (array1 and array2), and the objective is to return a new array representing the common elements between them. Each element in the resulting intersection array must appear only once, even if it appears multiple times in the original arrays.

Here's a breakdown of how the code achieves this goal:

  • Initialize a HashMap named map to keep track of elements from the first array (array1).
  • Populate this map using elements from array1 as keys, initially marking each with a count of 1 to indicate their presence.
  • Create an ArrayList named tempResult to temporarily store the intersection elements.
  • Iterate over the second array (array2). For each element:
    • Check if the element is in map and has a marker of 1.
    • If so, add the element to tempResult and update the element's marker in map to 0 to prevent duplication in case of further matches in array2.
  • Convert tempResult into an array of integers to match the function's return type using Java's stream API.

This approach ensures that the complexity is proportional to the size of array1 and array2, achieving efficient mapping and retrieval operations. By marking array elements dynamically in the hashmap, this code efficiently filters out duplicates and ensures only intersection results are considered.

Make sure to consider edge cases, such as either of the arrays being empty, which would simply return an empty intersection, as the code handles such situations by default due to natural flow and checks.

Comments

No comments yet.