Intersection of Two Arrays II

The problem requires returning the intersection of two integer arrays nums1 and nums2, where each element in the result must appear as many times as it shows in both arrays. You can use a dictionary to keep track of the counts of elements in one array and then use that information to find the intersection.

Here’s a step-by-step guide to solving the problem:

  1. Count Elements in nums1: Use a dictionary to count how many times each element appears in nums1.

  2. Find the Intersection: Iterate through nums2, and for each element, if it appears in the dictionary (and the count is greater than 0), add it to the result and decrease the count in the dictionary.

  3. Return the Result: The result is the list of elements that appear in both nums1 and nums2.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # Count the elements in nums1
        counts = {}
        for num in nums1:
            counts[num] = counts.get(num, 0) + 1

        # Find the intersection with nums2
        result = []
        for num in nums2:
            if counts.get(num, 0) > 0:
                result.append(num)
                counts[num] -= 1

        return result

Explanation:

  • The dictionary counts is used to keep track of how many times each number appears in nums1.
  • When iterating through nums2, if a number appears in counts (with a count greater than 0), it is part of the intersection, and you add it to the result and decrease the count in the dictionary.
  • The result list will include each intersecting number as many times as it appears in both arrays.

This approach ensures that the result reflects the actual intersection, including the number of occurrences, and meets the problem’s constraints.

Identifying Problem Isomorphism

“Intersection of Two Arrays” is isomorphic to “Intersection of Two Arrays II” (#350). Both problems involve finding the intersection of two arrays, meaning the elements that the two arrays have in common.

In “Intersection of Two Arrays”, the task is to find the distinct elements that both arrays have. In contrast, “Intersection of Two Arrays II” requires you to find all elements that both arrays have, including duplicates. In this sense, the latter problem can be seen as a generalized version of the former.

This is not an exact mapping. The major difference lies in handling duplicates. The first only counts distinct elements while the second also counts duplicates. Therefore, while the problems share a core concept and similar logic, the solutions might have subtle differences to accommodate these specific requirements.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        sortedArr1 = sorted(nums1)
        sortedArr2 = sorted(nums2)

        i = 0
        j = 0

        output = []
        while i < len(sortedArr1) and j < len(sortedArr2):
            if sortedArr1[i] < sortedArr2[j]:
                i += 1
            elif sortedArr2[j] < sortedArr1[i]:
                j += 1
            else:
                output.append(sortedArr1[i])
                i += 1
                j += 1
        return output

Problem Classification

This problem is a classical Array Manipulation problem with aspects of Frequency Counting. It requires elements from two arrays to be compared, counted, and collected based on the specific rules given, which makes it a sub-category of the more general Intersection of Two Arrays problems. It specifically involves concepts such as:

  1. Array Traversal: You need to traverse both arrays.
  2. Frequency Counting: You need to count the frequency of each element’s occurrence in both arrays.
  3. Intersection Calculation: You need to determine which elements appear in both arrays.
  4. Multiple Occurrence Handling: You must account for multiple occurrences of an element in the intersection array.

Language Agnostic Coding Drills

  1. Array Sorting: It’s important to know how to sort an array. In many languages, there’s a built-in function for this. The sorting is useful here to ensure that identical numbers from both arrays follow each other as we traverse the sorted arrays, making it easier to find common elements.

  2. Array Traversal with Two Pointers: This concept involves traversing two sorted arrays simultaneously with two separate indices (i and j in the provided code). The logic is such that if the element in the first array is smaller, we move the pointer in the first array forward. If the element in the second array is smaller, we move the pointer in the second array forward. If they’re equal, we know we’ve found a common element.

  3. Array Appending: Knowing how to add elements to an array is essential. Here, we’re adding common elements to an output array.

  4. Conditional Statements and Loops: The solution uses conditional statements (if and elif) inside a while loop to compare elements and increment pointers. Knowing how to construct these is fundamental to most programming tasks.

To solve the problem:

  1. Start by sorting both arrays. This makes it easier to find matching elements because they will appear in the same order in both arrays.
  2. Initialize two pointers (i and j) at the start of both sorted arrays.
  3. Use a while loop to go through the sorted arrays. This loop should continue until one of the pointers reaches the end of its array.
  4. In each iteration of the loop, compare the elements at the current indices of the sorted arrays.
  5. If they are equal, add them to the result array and move both pointers forward.
  6. If the element at the first pointer is less than the element at the second pointer, move the first pointer forward. This is because the first element is smaller and there’s no chance of finding this element in the second array as the second array is sorted too.
  7. If the element at the second pointer is less than the element at the first pointer, move the second pointer forward.
  8. At the end of the loop, return the result array, which will contain the intersection of the two input arrays.

Targeted Drills in Python

  1. Array Sorting:
1
2
3

nums = [5, 2, 9, 1, 5, 6]
nums.sort()
print(nums)  # Output: [1, 2, 5, 5, 6, 9]
  1. Array Traversal with Two Pointers:
1
2
3
4
5
6
7

nums1 = [1, 2, 3, 4, 5]
nums2 = [3, 4, 5, 6, 7]
i, j = 0, 0
while i < len(nums1) and j < len(nums2):
    print(nums1[i], nums2[j])
    i += 1
    j += 1
  1. Array Appending:
1
2
3

nums = [1, 2, 3]
nums.append(4)
print(nums)  # Output: [1, 2, 3, 4]
  1. Conditional Statements and Loops:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

nums1 = [1, 2, 3, 4, 5]
nums2 = [3, 4, 5, 6, 7]
i, j = 0, 0
while i < len(nums1) and j < len(nums2):
    if nums1[i] < nums2[j]:
        i += 1
    elif nums1[i] > nums2[j]:
        j += 1
    else:
        print("Match:", nums1[i])
        i += 1
        j += 1

Now, to combine all these into an integrated drill, we can use the following code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def intersect(nums1, nums2):
    nums1.sort()
    nums2.sort()

    i, j = 0, 0
    result = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i] < nums2[j]:
            i += 1
        elif nums1[i] > nums2[j]:
            j += 1
        else:
            result.append(nums1[i])
            i += 1
            j += 1

    return result

nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(intersect(nums1, nums2))  # Output: [2, 2]