Problem

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.

Examples

Example 1:

1
2

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

1
2
3

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.

Follow ups

What if arrays are sorted

We have solved it here, Intersection of Two Sorted Arrays, and also in method 2.

What if elements in nums2 cannot fit in memory

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?

  1. Store nums1 in a Map.
  2. Split nums2 into n equal chunks.
  3. Load one chunk of nums2 into memory at a time and check for intersections with the Map. If the intersection result becomes too large for memory, save the partial result to disk and proceed with the process.

What if elements in both nums1 and nums2 cannot fit in memory

  1. Utilize external sorting to sort nums1.
  2. Similarly, apply external sorting to sort nums2 (this can theoretically be done concurrently with the sorting of nums1).
  3. Implement the two-pointer method to find the intersection:
    • Partition nums1 into chunks that use no more than ~10% of memory.
    • Similarly, partition nums2 into chunks that also use no more than ~10% of memory.
    • Dedicate the remaining ~80% of memory for the intersection results.
    • Simultaneously load one chunk of nums1 and one chunk of nums2 into memory.
    • If the intersection becomes too large for memory, save the partial result to disk and proceed with the algorithm.
Similar Problems

Solution

Method 1 - Frequency map

Here are the steps we can follow:

  1. Create the frequency map on nums1
  2. Now, loop over nums2 and check if element exists in map
    1. If it does, add to answer list and reduce the frequency in frequency map
    2. If it doesn’t exist in map, just continue
  3. Finally convert the answer list to array and return

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {

	public int[] intersect(int[] nums1, int[] nums2) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();

		// Populate the map with counts of each element in nums1
		for (int num: nums1) {
			map.put(num, map.getOrDefault(num, 0) + 1);
		}

		List<Integer> list = new ArrayList<Integer>();

		// Find intersecting elements and update the map
		for (int num: nums2) {
			if (map.containsKey(num)) {
				list.add(num);

				// Decrement the count or remove the element from the map if count becomes 0
				map.put(num, map.get(num) - 1);

				if (map.get(num) == 0) {
					map.remove(num);
				}
			}
		}

		// Convert list to an array
		int[] ans = new int[list.size()];
		int i = 0;

		for (int num: list) {
			ans[i++] = num;
		}

		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(m + n) where m and n is size of of nums1 and nums2.
  • 🧺 Space complexity: O(m + n)

Method 2 - Sorting and two pointer scan

Here are the steps we can follow:

  1. Sort both arrays
  2. Now start 2 pointers i and j on both the arrays.
    1. If the elements are not equal, move the pointer forward with smaller value
    2. If the nums[i] and nums[j] elements are equal, we add to answer list
  3. Convert answer list to array and return

If the arrays are sorted, we just need to follow the steps from step 2: Intersection of Two Sorted Arrays

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class Solution {

	public int[] intersect(int[] nums1, int[] nums2) {
		Arrays.sort(nums1);
		Arrays.sort(nums2);

		ArrayList<Integer> list = new ArrayList<Integer>();
		int i = 0, j = 0;

		while (i < nums1.length && j  <  nums2.length) {
			if (nums1[i]<nums2[j]) {
				i++;
			} else if (nums1[i] > nums2[j]) {
				j++;
			} else {
				list.add(nums1[i]);
				i++;
				j++;
			}
		}

		int[] result = new int[list.size()];
		int k = 0;
		while (k < list.size()) {
			result[k] = list.get(k);
			k++;
		}

		return result;
	}
}

Complexity

  • ⏰ Time complexity: O(m log m + n log n) where m and n is size of of nums1 and nums2. Mainly, for sorting two arrays and O(n log m) for searching elements elements in nums1 in nums2.
  • 🧺 Space complexity: O(n) for using ansList