Intersection of Two Arrays

title: Intersection of Two Arrays tags: intersection

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

Constraints

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

Solution

Take the first element in the first array and check if it is found in the second array. Requires scanning the entire second array.

1 -> 0..n-1
2 -> 0..n-1

...
   
n-1 -> 0..n-1

One index for nums1: Fix it in the outer loop (0). Second index for nums2: Vary the index from 0..end of array. Nested for loops.

T: O(N^2)
S: O(1)

How can we go from quadratic to O(n log n) ? Use sorting as a preprocessing step to improve the time complexity.

Transform and Conquer can be applied for this problem. In this case the transform step is presorting. Time complexity of sorting: O(n log n).

nums1 = [1,1,2,2], nums2 = [2,2]

We avoid repeated work. This is better than the brute force. We need to process all elements until we have exhausted all the elements in the smallest array. We have to skip duplicate numbers.

T: O(n log n) + O(n)
S: O(1)

Another approach is Binary Search, in this case the time and complexity is:

T: O(n log n) + O(n log n)
S: O(1)

Another Transform and Conquer approach involves representation change where we change the input array to set. In this case the set search takes: O(1) in time complexity.

T: O(m+n)
S: O(m+n)

Two Sets Solution

 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

def set_intersection(set1, set2)
  output = []
  i = 0
  
  set1.each do |element|
    if set2.include?(element)
      output[i] = element
      i += 1
    end
  end
    
  output
end

# @param {Integer[]} nums1
# @param {Integer[]} nums2
# @return {Integer[]}
def intersection(nums1, nums2)
  set1 = Set.new(nums1)
  set2 = Set.new(nums2)
    
  if set1.size < set2.size
    return set_intersection(set1, set2)
  else
    return set_intersection(set2, set1) 
  end
end

Language Builtin Set Intersection

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

# @param {Integer[]} nums1
# @param {Integer[]} nums2
# @return {Integer[]}
def intersection(nums1, nums2)
  # Transform: Representation change
  # Cost of transformation: O(n + m)
  set1 = Set.new(nums1)
  set2 = Set.new(nums2)

  # Cost of finding intersection
  set = set1 & set2    
  # Conversion from set to array is at least linear
  return set.to_a
end

The problem is about finding the intersection of two integer arrays, nums1 and nums2. The intersection means the set of unique elements that appear in both arrays. Here’s a guide to solving this problem:

  1. Convert Arrays to Sets: You can use the Python set data structure to convert both nums1 and nums2 into sets. This will remove any duplicate elements within each array.

  2. Find the Intersection: Use the & operator to find the intersection of the two sets. This will give you a new set containing only the elements that are present in both original sets.

  3. Convert to a List: Finally, convert the set of intersecting elements to a list and return it.

Here’s a code implementation of the above approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # Convert arrays to sets
        set1 = set(nums1)
        set2 = set(nums2)

        # Find the intersection
        intersecting_set = set1 & set2

        # Convert to a list and return
        return list(intersecting_set)

Explanation:

  • By converting the arrays to sets, you ensure that each number is represented only once within each array.
  • The & operator is used to find the intersection of two sets, giving you the set of numbers that appear in both nums1 and nums2.
  • The result is then converted to a list, as required by the problem statement.

This solution is simple and efficient, meeting the problem’s constraints and achieving the desired result.

Identifying Problem Isomorphism

“Intersection of Two Arrays” (#349) is isomorphic to “Intersection of Two Linked Lists” (#160). Both problems share a core concept: finding the intersection between two data structures.

While “Intersection of Two Arrays” requires finding the common elements between two arrays, “Intersection of Two Linked Lists” requires finding the intersecting node in two linked lists. Though the specific elements being examined (array elements versus linked list nodes) and the final output differ, the approach to the problem can be quite similar: traversing the two data structures and comparing elements to identify intersections.

This is an approximate mapping. In “Intersection of Two Arrays”, we’re dealing with a simple list of integers and looking for common values, whereas in “Intersection of Two Linked Lists”, we’re dealing with a more complex data structure and looking for a common node (not just the node’s value). So while the problems are similar, the solutions would not be interchangeable without significant adaptation.

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

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()

        ans = []
        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

Problem Classification

This problem falls into the following categories:

  1. Array Manipulation: The problem involves working with arrays (or lists in Python), which includes iterating over them and applying certain conditions.

  2. Set Theory: The problem specifically asks for the intersection of two sets, which is a fundamental concept in set theory.

  3. Data Structures: The most efficient solution to this problem involves using specific data structures, like sets in Python, which have built-in methods for intersection. This falls under general data structure manipulation and usage.

  4. Element Uniqueness: The problem asks for each element in the result to be unique, which is a common condition in problems related to set theory and array manipulation.

Language Agnostic Coding Drills

Here is how you can break down this problem:

  1. Understanding Data Structures: Understanding how data structures work is critical to this problem, especially how dictionaries and lists are used and manipulated in a programming language.

    • Drill: Practice creating dictionaries and lists, adding items to them, removing items from them, and looking up items in them.

  2. Iterating through Lists: This problem involves going through each item in the two given lists.

    • Drill: Write a loop that goes through each item in a list and prints it out.

  3. Dictionary Manipulation: In this problem, a dictionary is used to keep track of the numbers in the first list.

    • Drill: Practice creating a dictionary from a list, where each item in the list becomes a key in the dictionary, and the value is some function of the item (like its square).

  4. Checking for Existence in Dictionary: You will need to check whether an item from the second list exists as a key in the dictionary.

    • Drill: Given a dictionary and a potential key, write a statement that checks whether the key exists in the dictionary.

  5. Using Dictionary Values: In this problem, dictionary values are used to keep track of whether a number has already been added to the result list.

    • Drill: Given a dictionary and a key, practice accessing the value associated with that key and manipulating it (like incrementing it or setting it to a new value).

  6. Building Result List: The result of this problem is a list, which must be built up one item at a time as you go through the second list.

    • Drill: Practice adding items to a list one at a time inside a loop.

  7. Combining Above Concepts: The final solution involves creating a dictionary from the first list, then iterating through the second list and using the dictionary to decide whether to add each item to the result list.

    • Drill: Combining the previous drills, create a dictionary from a list of numbers, then iterate through a second list of numbers, adding each number to a new list only if it’s in the dictionary.

These drills start from the basics of working with lists and dictionaries, and build up to the full complexity of the problem. Each one provides a piece of the final solution.

Targeted Drills in Python

  1. Understanding Data Structures:

    • Drill Code:
       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

      # Creating a dictionary and adding items
d = {"key1": "value1", "key2": "value2"}
print(d)

# Adding an item to the dictionary
d["key3"] = "value3"
print(d)

# Removing an item from the dictionary
del d["key1"]
print(d)

# Creating a list and adding items
l = ["item1", "item2", "item3"]
print(l)

# Adding an item to the list
l.append("item4")
print(l)

# Removing an item from the list
l.remove("item1")
print(l)

  2. Iterating through Lists:

    • Drill Code:
      1
2
3
4

      l = [1, 2, 3, 4, 5]

for item in l:
    print(item)

  3. Dictionary Manipulation:

    • Drill Code:
      1
2
3

      l = [1, 2, 3, 4, 5]
d = {item: item**2 for item in l}
print(d)

  4. Checking for Existence in Dictionary:

    • Drill Code:
      1
2
3
4

      d = {"key1": "value1", "key2": "value2"}

if "key1" in d:
    print("Key exists in the dictionary")

  5. Using Dictionary Values:

    • Drill Code:
      1
2
3
4

      d = {"key1": 1, "key2": 2}

d["key1"] += 1
print(d["key1"])

  6. Building Result List:

    • Drill Code:
      1
2
3
4

      l = []
for i in range(5):
    l.append(i)
print(l)

  7. Combining Above Concepts:

    • Drill Code:
       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

      l1 = [1, 2, 3, 4, 5]
l2 = [3, 4, 5, 6, 7]
d = {item: 1 for item in l1}
result = []

for item in l2:
    if item in d and d[item] == 1:
        result.append(item)
        d[item] -= 1

print(result)

CHANGE DRILLS - EXTRACT FROM THE SOLUTION AT THE TOP