Skip to content

350. Intersection Of Two Arrays II

Array Hash Table Two Pointers Binary Search Sorting

Problem - Intersection Of Two Arrays II

Easy

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?

Solutions

 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
public class Solution {
    public int[] Intersect(int[] nums1, int[] nums2) {
        Dictionary<int, int> elementCounts = new Dictionary<int, int>();

        // Count occurrences of each element in nums1
        foreach (int num in nums1)
        {
            if (elementCounts.ContainsKey(num))
            {
                elementCounts[num]++;
            }
            else
            {
                elementCounts.Add(num, 1);
            }
        }

        List<int> commonElements = new List<int>();

        // Find common elements in nums2
        foreach (int num in nums2)
        {
            if (elementCounts.ContainsKey(num) && elementCounts[num] > 0)
            {
                commonElements.Add(num);
                elementCounts[num]--; // Decrement the count
            }
        }

        return commonElements.ToArray();
    }



}

Submission Stats:

  • Runtime: 112 ms (5.44%)
  • Memory: 46.6 MB (99.85%)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        count = Counter(nums1)
        result = []

        for val in nums2:
            if count[val]:
                result.append(val)
                count[val] -= 1

        return result

Submission Stats:

  • Runtime: 3 ms (40.45%)
  • Memory: 18 MB (26.59%)