Problem Statement

Given two integer arrays, implement a function to compute their intersection. The result should contain only unique elements, and the order of the output is not important.

Python Solution

from typing import List

class ArrayIntersection:
    def find_intersection(self, arr1: List[int], arr2: List[int]) -> List[int]:
        # Initialize a dictionary to track elements from the first array
        element_counter = {}
        
        # Populate the dictionary with elements from arr1
        for value in arr1:
            # Increment count for each occurrence, defaulting to 0 if not present
            element_counter[value] = element_counter.get(value, 0) + 1
        
        # Use a set to store intersecting elements without duplicates
        intersection_set = set()
        
        # Check each element in arr2 against the dictionary
        for value in arr2:
            if value in element_counter:
                intersection_set.add(value)
                # Remove the element to prevent duplicate matches
                del element_counter[value]
        
        # Convert the set to a list for the final result
        return list(intersection_set)

Solution Breakdown

This aproach uses a hash map (dictionary) to efficiently determine common elements between two arrays. The process is as follows:

1. Hash Map Construction:

   • A dictionary named element_counter is created to store elements from the first array (arr1).
   • Each element from arr1 serves as a key, with its value representing the count of occurrences. The get method is used to safely increment the count, initializing it to 0 if the key is absent.

2. Intersection Identification:

   • A set called intersection_set is initialized to hold the intersection results, ensuring uniqueness.
   • The second array (arr2) is traversed. For each element, if it exists as a key in element_counter, it is added to intersection_set.
   • The element is then removed from element_counter using del to avoid redundant additions.

3. Result Preparation:

   • The set is converted to a list and returned as the final output.

Key Code Explanation

The line element_counter[value] = element_counter.get(value, 0) + 1 is central to building the hash map. Here’s a step-by-step interpretation:

• element_counter.get(value, 0) retrieves the current count for value from the dictionary. If value is not found, it returns the default value 0.
• Adding 1 increments this count, accounting for the current occurrence of value in arr1.
• The updated count is then assigned back to element_counter[value], effectively tracking the frequency of each element.

This concise sttaement combines checking to an existing key, handling missing keys, and updating the count in a single operation.