We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Intersection of Two Arrays

Number: 349

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Microsoft, Meta, Criteo, Nvidia, Apple, Adobe, Yandex, LinkedIn, J.P. Morgan, Two Sigma, Wix

Problem Description

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.

Key Insights

  • Use a hash set for efficient O(1) membership tests.
  • Converting one array into a set eliminates duplicates and facilitates quick lookups.
  • Iterate through the other array and add common elements to a result set ensuring uniqueness.
  • Alternative approaches include sorting and using two pointers or binary search, but a hash set approach offers a clear O(m+n) solution.

Space and Time Complexity

Time Complexity: O(m + n), where m and n are the lengths of nums1 and nums2 respectively. Space Complexity: O(min(m, n)), due to storing elements in the sets.

Solution

Convert one of the arrays (e.g., nums1) into a set to allow constant time existence checks. Then iterate over the elements of nums2, checking if each element is part of the nums1 set. When an element is found in both arrays, add it to a result set to ensure uniqueness. Finally, convert this set back to an array or list to return the result. This approach guarantees that every element is processed only once and automatically handles duplicate values.

Code Solutions

# Function to find the intersection of two arrays
def intersection(nums1, nums2):
    # Convert nums1 to a set for O(1) lookups
    nums1_set = set(nums1)
    # Initialize an empty set to store unique intersection elements
    intersection_set = set()
    
    # Iterate through each element in nums2
    for num in nums2:
        # If the element is found in nums1_set, add it to the intersection_set
        if num in nums1_set:
            intersection_set.add(num)
    
    # Return the intersection as a list
    return list(intersection_set)

# Example usage:
print(intersection([4, 9, 5], [9, 4, 9, 8, 4]))  # Expected output: [9, 4] (order may vary)
← Back to All Questions