Vultr DocsLatest Content

Intersection of Two Arrays II

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

Problem Statement

Given two integer arrays nums1 and nums2, the objective is to find the intersection of these two arrays. The term "intersection" in this context refers to elements that are present in both arrays. Crucially, if an element appears multiple times in both arrays, it should appear in the intersection array a number of times equal to the minimum number of times it appears in either array. The resultant intersection array can be returned in any order.

Examples

Example 1

Input:

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

Output:

[2,2]

Example 2

Input:

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

Output:

[4,9]

Explanation:

[9,4] is also accepted.

Constraints

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

Approach and Intuition

The given problem can be tackled effectively using the following steps:

  1. Use a hashmap to count the occurrences of each number in the first array (nums1).
  2. Initialize an empty list to store the intersecting elements.
  3. Iterate over the second array (nums2) and for each element:
    • Check if the element is in the hashmap and has a non-zero count, which means it occurs in both arrays.
    • If present, append it to the result list and decrement the count in the hashmap.
    • This ensures that an element is added to the result list no more times than it appears in both arrays.

By using this approach, we can ensure that the intersection includes each element the minimum number of times it appears in both arrays. This method leverages hashmap for efficient lookup and count decrement operations, allowing us to optimize the solution for potentially large arrays while adhering to the constraints provided.

Solutions

  • C++
  • Java
cpp 
vector<int> find_intersection(vector<int>& set1, vector<int>& set2) {
    sort(begin(set1), end(set1));
    sort(begin(set2), end(set2));
    int a = 0, b = 0, c = 0;
    while (a < set1.size() && b < set2.size()) {
        if (set1[a] < set2[b]) {
            ++a;
        } else if (set1[a] > set2[b]) {
            ++b;
        } else {
            set1[c++] = set1[a++];
            ++b;
        }
    }
    return vector<int>(begin(set1), begin(set1) + c);
}

This summary outlines a solution for finding the intersection of two integer arrays set1 and set2. The solution is implemented in C++.

The function find_intersection starts by sorting both arrays set1 and set2. This facilitates the use of a two-pointer technique, which efficiently finds common elements. Here is a step-by-step breakdown of the process:

  1. Sort both input arrays, set1 and set2.
  2. Initialize three integer variables a, b, and c to serve as pointers and counters.
  3. Run a while loop until one of the pointers a or b exceeds the size of set1 or set2 respectively.
    • If the current element in set1 is lesser than the current element in set2, increment pointer a to move to the next element in set1.
    • If the current element in set1 is greater than the current element in set2, increment pointer b to move to the next element in set2.
    • If the elements at pointers a and b are equal, it indicates a common element. Store this element in set1[c] and increment all pointers a, b, and c.
  4. The loop terminates when the end of either array is reached. At this point, the common elements have been collected from the beginning up to the c-th position in set1.
  5. Construct a new vector from the first c elements of set1 to return only the intersected values.

This method is effective and efficient for finding intersected values between two arrays with minimal space usage by cleverly utilizing the input arrays for output.

java 
public int[] findIntersection(int[] array1, int[] array2) {
    Arrays.sort(array1);
    Arrays.sort(array2);
    int index1 = 0, index2 = 0, index3 = 0;
    while (index1 < array1.length && index2 < array2.length) {
        if (array1[index1] < array2[index2]) {
            index1++;
        } else if (array1[index1] > array2[index2]) {
            index2++;
        } else {
            array1[index3++] = array1[index1++];
            index2++;
        }
    }
    return Arrays.copyOfRange(array1, 0, index3);
}

The provided Java solution implements a function to find the intersection of two arrays, where each element in the result should appear as many times as it shows in both arrays. The method, findIntersection, takes two integer arrays as input.

  • Start by sorting both arrays. This ensures that identical elements are lined up, making comparison straightforward.
  • Initialize three indices to zero: index1 for array1, index2 for array2, and index3 for tracking the position in array1 to store intersecting elements.
  • Utilize a while loop to traverse both arrays until either of the arrays is completely processed. Inside the loop:
    • Compare elements at the current index of both arrays:
      • If the element in array1 is less than in array2, increment index1 to move to the next element in array1.
      • If the element in array1 is more than in array2, increment index2 to move to the next element in array2.
      • If the elements are equal, this means an intersection is found:
        • Store the intersecting element in array1 at the current position of index3.
        • Increment both index1 and index2 to continue searching for other intersections.
        • Increment index3 to prepare a position for the next potential intersection.
  • After exiting the loop, use Arrays.copyOfRange to extract the intersecting elements from array1, starting from the 0th index up to index3.
  • Return the new array which contains all the intersecting elements.

This approach guarantees that the space complexity is handled efficiently by reusing array1 for the result storage, and the time complexity largely depends on the sorting process, making it O(n log n) due to the sorting of the arrays.

Comments

No comments yet.