> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0350-intersection-of-two-arrays-ii.md).

# 0350. Intersection of Two Arrays II

<https://leetcode.com/problems/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 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?

## ac1: map

```java
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // edge case
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return new int[0];

        int[] big = nums1.length > nums2.length ? nums1 : nums2;
        int[] small = nums1.length > nums2.length ? nums2 : nums1;

        // record nums in smaller one
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < small.length; i++) {
            map.put(small[i], map.getOrDefault(small[i], 0) + 1);
        }

        List<Integer> res = new ArrayList<>();
        // compair with bigger one
        for (int i = 0; i < big.length; i++) {
            if (map.getOrDefault(big[i], 0) > 0) {
                res.add(big[i]);
                map.put(big[i], map.get(big[i]) - 1);
            }
        }

        // build result
        int[] result = new int[res.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = res.get(i);
        }

        return result;
    }
}
```

## ac2: sort + 2 pointers

```java
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // edge case
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return new int[0];

        Arrays.sort(nums1);
        Arrays.sort(nums2);


        List<Integer> res = new ArrayList<>();
        // 2 pointers
        int p1 = 0, p2 = 0;
        while (p1 < nums1.length && p2 < nums2.length) {
            if (nums1[p1] == nums2[p2]) {
                res.add(nums1[p1]);
                p1++;
                p2++;
            } else if (nums1[p1] > nums2[p2]) {
                p2++;
            } else if (nums1[p1] < nums2[p2]) {
                p1++;
            }
        }

        // build result
        int[] result = new int[res.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = res.get(i);
        }

        return result;
    }
}
```