:orphan:

Intersection Of Two Arrays Ii
=============================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/intersection-of-two-arrays-ii/

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?

.. highlight:: python

Pattern
-------
Array, Hash Table, Two Pointers, Binary Search, Sorting

Solution
--------
Count the number of times each number appears in each array in 2 dictionaries
``dict1`` and ``dict2``. For each ``key`` in ``dict1`` and ``dict2``, add
``key`` repeated ::

    min(dict1[key], dict2[key])

times to the intersection
list.

Code
----

.. literalinclude:: ../problems/easy/intersection-of-two-arrays-ii/intersection_of_two_arrays_ii__approach_1.py
    :language: python
    :lines: 9-

Test
----
>>> from intersection_of_two_arrays_ii__approach_1 import intersect
>>> intersect([1,2,2,1], [2,2])
[2, 2]
>>> intersect([4,9,5], [9,4,9,8,4])
[4, 9]

Complexity
----------
| :math:`m` is the length of ``nums1`` and :math:`n` is the length of ``nums2``
| Time: :math:`O(m + n)` — count each array and then iterate through the keys of the smaller dictionary
| Auxiliary Space: :math:`O(m + n)` — 2 dictionaries store at most :math:`m` and :math:`n` key-value pairs respectively

.. autofunction:: intersection_of_two_arrays_ii__approach_1.intersect

.. autofunction:: intersection_of_two_arrays_ii__approach_1.counts