Intersection of Two Arrays II

EASY

Description

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

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

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?
What if nums1's size is small compared to nums2's size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Approaches

Checkout 3 different approaches to solve Intersection of Two Arrays II. Click on different approaches to view the approach and algorithm in detail.

Sorting with Two Pointers

This approach first sorts both arrays. Then, it uses two pointers to iterate through the sorted arrays simultaneously. By comparing the elements at the pointers, we can find the common elements efficiently in a single pass after sorting.

Algorithm

Sort both input arrays, nums1 and nums2.
Initialize two pointers, i = 0 for nums1 and j = 0 for nums2.
Initialize an empty list intersection.
While i < nums1.length and j < nums2.length:
- If nums1[i] < nums2[j], increment i.
- Else if nums1[i] > nums2[j], increment j.
- Else (if nums1[i] == nums2[j]):
  - Add nums1[i] to the intersection list.
  - Increment both i and j.
Convert the intersection list to an array and return it.

A more efficient way to solve the problem is to first sort both arrays. Once sorted, we can use a two-pointer technique. We initialize one pointer at the beginning of each array. We then compare the elements at the two pointers:

If the element in nums1 is smaller, we advance the pointer for nums1 because we need to find a larger value to match the current element in nums2.
If the element in nums2 is smaller, we advance the pointer for nums2 for the same reason.
If the elements are equal, we have found a common element. We add it to our result list and advance both pointers to look for the next potential match. This process continues until one of the pointers goes past the end of its array.

This approach is particularly effective if the arrays are already sorted (a follow-up question), as the sorting step can be skipped, making the algorithm run in linear time.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int i = 0, j = 0;
        List<Integer> intersection = new ArrayList<>();
        
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                intersection.add(nums1[i]);
                i++;
                j++;
            }
        }
        
        // Convert List to array
        int[] result = new int[intersection.size()];
        for (int k = 0; k < intersection.size(); k++) {
            result[k] = intersection.get(k);
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n log n + m log m), where `n` and `m` are the lengths of the arrays. The dominant operation is sorting. The two-pointer scan takes linear time, O(n + m).Space Complexity: O(log n + log m) to O(n + m), depending on the implementation of the sorting algorithm used by the language's standard library. This does not include the space for the result list, which is O(min(n, m)).

Pros and Cons

Pros:

Very efficient if the arrays are already sorted (O(n + m) time).
Space-efficient, especially if an in-place sort with logarithmic space is used.

Cons:

The sorting step can be costly if the arrays are large and unsorted.
Modifies the original arrays if sorted in-place, which might not be desirable.

Code Solutions

Checking out 5 solutions in different languages for Intersection of Two Arrays II. Click on different languages to view the code.

public class Solution {
    public int[] Intersect(int[] nums1, int[] nums2) {
        HashSet < int > hs1 = new HashSet < int > (nums1.Concat(nums2).ToArray());
        Dictionary < int, int > dict = new Dictionary < int, int > ();
        List < int > result = new List < int > ();
        foreach(int x in hs1) {
            dict[x] = 0;
        }
        foreach(int x in nums1) {
            if (dict.ContainsKey(x)) {
                dict[x] += 1;
            } else {
                dict[x] = 1;
            }
        }
        foreach(int x in nums2) {
            if (dict[x] > 0) {
                result.Add(x);
                dict[x] -= 1;
            }
        }
        return result.ToArray();
    }
}

Video Solution

Watch the video walkthrough for Intersection of Two Arrays II

Algorithms:

Binary SearchSorting

Patterns:

Two Pointers

Data Structures:

ArrayHash Table

Companies:

Yandex |