Welcome to Subscribe On Youtube
350. Intersection of Two Arrays II
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 tonums2
'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?
Solutions
HashSet
The previous expansion of 349 Intersection of Two Arrays, the difference is that this question allows to return repeated numbers
, and returns as many as possible.
HashMap to establish the mapping between the characters in nums1 and the number of occurrences, and then traverse the nums2 array.
If the number of the current character in the HashMap is greater than 0, add this character to the result, and then the corresponding value of the HashMap will be decremented by 1.
Two pointers
Sort the two arrays first, and then use two pointers to point to the starting positions of the two arrays,
 If the numbers pointed to by the two pointers are equal, it is stored in the result, and both pointers are incremented by 1,
 If the number pointed to by the first pointer is large, the second pointer is incremented by 1, and vice versa
Follow up
1. If the given array is already sorted:
If both nums1
and nums2
are sorted, you can use a twopointer technique
to improve the time complexity to O(n + m)
, where n and m are the lengths of the two arrays. This approach eliminates the need for additional space required for hash maps in the unsorted case.
2. If nums1
’s size is small compared to nums2
’s size:
If one array is significantly smaller than the other, it’s more efficient to use a hash map
for the smaller array. This reduces the space complexity and potentially the time complexity since you iterate over and hash only the smaller array and then iterate over the larger array to check for intersections.
3. If elements of nums2
are stored on disk, and the memory is limited:
In this scenario, external sorting
and the twopointer technique
can be used.
Process nums1
into a hash map or sort it if not already sorted. For nums2
, use external sorting algorithms that break the data into chunks that fit into memory, sort each chunk, and then merge them. This way, you can sort nums2
without loading it entirely into memory. After sorting, you can stream nums2
from disk and use the twopointer technique or binary search (if nums1
is hashed) to find intersections without exceeding memory limits.
For massive datasets that cannot fit into memory (like nums2
in this case), consider using database solutions
designed for handling largescale data or big data technologies like Hadoop or Spark, which provide mechanisms for distributed data processing.
3.1 More on external sorting  memory is limited
External sorting is a class of algorithms used to handle massive amounts of data that do not fit into a computer’s main memory (RAM) but instead are stored on a slower, external memory such as a hard disk drive (HDD) or solidstate drive (SSD). This is particularly useful for sorting large files that exceed the capacity of the system’s RAM. The most common external sorting algorithm is the external merge sort, which involves the following steps:
1. Divide:
 The large dataset is divided into smaller chunks, each of which can fit into the available RAM.
 These chunks are read into memory one at a time.
2. Sort:
 Each chunk is sorted in memory using an efficient internal sorting algorithm, like quicksort or mergesort.
 After sorting, the sorted chunks are written back to the external storage.
3. Merge:
 The sorted chunks are then merged into a single, fully sorted file.
 This merge process is done in a way that always maintains a manageable number of chunks in memory, regardless of the total size of the dataset.
Example of External Merge Sort:
Assume you have 1GB of data to sort, but only 256MB of RAM available.
Divide:
 Break the 1GB file into 4 chunks of 256MB each.
 Read the first 256MB chunk into RAM.
Sort:
 Sort this chunk using an inmemory sorting algorithm (like mergesort).
 Write the sorted chunk back to disk.
 Repeat this process for the remaining chunks.
Merge:
 Read the first part of each sorted chunk into RAM and merge them, creating a new sorted sequence of data. Given the RAM limitation, you might only be able to read a small portion of each chunk at a time.
 Write the merged sequence back to disk.
 If there was more than one value from each chunk in RAM, repeat the merge process, reading the next values from the chunks as needed until all chunks are fully merged into a single sorted sequence.
Efficiency Tips:
 To reduce disk I/O, which is typically the bottleneck in external sorting, it’s essential to optimize how data is read from and written to disk. For example, using larger buffers can reduce the number of disk accesses.
 Multiway merges, where more than two chunks are merged at once, can significantly reduce the total number of merging passes needed.
Applications:
 External sorting is crucial in databases for sorting large tables and in big data applications where datasets far exceed the available memory.
 Tools and frameworks that handle big data, like Hadoop and Spark, implement their versions of external sorting to distribute the sorting process across multiple machines, further scaling the ability to sort massive datasets efficiently.

class Solution { public int[] intersect(int[] nums1, int[] nums2) { Map<Integer, Integer> counter = new HashMap<>(); for (int num : nums1) { counter.put(num, counter.getOrDefault(num, 0) + 1); } List<Integer> t = new ArrayList<>(); for (int num : nums2) { if (counter.getOrDefault(num, 0) > 0) { t.add(num); counter.put(num, counter.get(num)  1); } } int[] res = new int[t.size()]; for (int i = 0; i < res.length; ++i) { res[i] = t.get(i); } return res; } }

class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { unordered_map<int, int> counter; for (int num : nums1) ++counter[num]; vector<int> res; for (int num : nums2) { if (counter[num] > 0) { counter[num]; res.push_back(num); } } return res; } };

class Solution: def intersect(self, nums1: List[int], nums2: List[int]) > List[int]: counter = Counter(nums1) res = [] for num in nums2: if counter[num] > 0: res.append(num) counter[num] = 1 return res ############ class Solution(object): def intersect(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ ans = [] nums1.sort() nums2.sort() i = j = 0 while i < len(nums1) and j < len(nums2): if nums1[i] < nums2[j]: i += 1 elif nums1[i] > nums2[j]: j += 1 else: ans.append(nums1[i]) i += 1 j += 1 return ans

func intersect(nums1 []int, nums2 []int) []int { counter := make(map[int]int) for _, num := range nums1 { counter[num]++ } var res []int for _, num := range nums2 { if counter[num] > 0 { counter[num] res = append(res, num) } } return res }

function intersect(nums1: number[], nums2: number[]): number[] { const map = new Map<number, number>(); for (const num of nums1) { map.set(num, (map.get(num) ?? 0) + 1); } const res = []; for (const num of nums2) { if (map.has(num) && map.get(num) !== 0) { res.push(num); map.set(num, map.get(num)  1); } } return res; }

/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ var intersect = function (nums1, nums2) { const counter = {}; for (const num of nums1) { counter[num] = (counter[num]  0) + 1; } let res = []; for (const num of nums2) { if (counter[num] > 0) { res.push(num); counter[num] = 1; } } return res; };

class Solution { /** * @param Integer[] $nums1 * @param Integer[] $nums2 * @return Integer[] */ function intersect($nums1, $nums2) { $rs = []; for ($i = 0; $i < count($nums1); $i++) { $hashtable[$nums1[$i]] += 1; } for ($j = 0; $j < count($nums2); $j++) { if (isset($hashtable[$nums2[$j]]) && $hashtable[$nums2[$j]] > 0) { array_push($rs, $nums2[$j]); $hashtable[$nums2[$j]] = 1; } } return $rs; } }

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

use std::collections::HashMap; impl Solution { pub fn intersect(nums1: Vec<i32>, nums2: Vec<i32>) > Vec<i32> { let mut map = HashMap::new(); for num in nums1.iter() { *map.entry(num).or_insert(0) += 1; } let mut res = vec![]; for num in nums2.iter() { if map.contains_key(num) && map.get(num).unwrap() != &0 { map.insert(num, map.get(&num).unwrap()  1); res.push(*num); } } res } }