Intersection of Two Arrays (via Leetcode)¶
Date published: 2020-04-07
Category: Python
Subcategory: Beginner Algorithms
Tags: functions, loops, lists, sets
This question can be found on Leetcode.
Problem statement:
Given two arrays, write a function to compute their intersection.
Test Cases¶
# assert intersection([1, 2, 3, 4], [2, 3]) == [2, 3]
Only the values 2 and 3 appear in both lists.
# assert intersection([1, 3, 3, 4], [3, 0, 5]) == [3]
Only the unique value of 3 appears in both lists.
# assert intersection([1, 2], [4, 5]) == []
There are no common values between the lists so the function returns an empty list.
Pseudocode for Solution #1: the Brute Force Way¶
This pseudocode below is my first brute force approach that uses simple syntax, data structures and methods to compute the solution. There is minimal logic.
# create a function with two arguments - each as an input list of integers
# cast each input list to a set
# a set in Python is an unordered collection with no duplicate elements
# sets have an intersection method to return unique elements found in both sets
# intersection_set = set1.intersection(set2)
# cast intersection_set as list
# return list
Complexity for Solution #1¶
Let n be the length of items in one input list and m be the length of items in the other input list.
Space Complexity¶
I create two sets - one of length n and the other of length m. This space complexity is O(m+n).
I also create the final intersection_list which could be up to n or m values - depending on which one is smaller in length. Let's call this an O(n) operation.
Total space complexity is O(2n) + O(m).
Time Complexity¶
To create a set, obfuscated from my code, there is an iteration of a list of O(n) and each element is added to the set in an O(1) operation. Therefore the total operation is O(n).
In my solution, creation of the sets are an O(n) and O(m) time complexity operation respectively.
In the intersection() method, for each value in num1, we have to check if the value exists in num2. Therefore, the operation is O(m*n).
Total time complexity is: O(n) + O(m) + O(m*n)
Code for Solution #1: the Brute Force Way¶
def intersection(nums1, nums2):
set1 = set(nums1)
set2 = set(nums2)
intersection_set = set1.intersection(set2)
intersection_list = list(intersection_set)
return intersection_list
Verify Test Cases for Solution #1¶
I added some additional tests cases beyond the ones stated above.
assert intersection([1, 2], [4, 5]) == []
assert intersection([1, 3, 3, 4], [3, 0, 5]) == [3]
assert intersection([1, 2, 3, 4], [2, 3]) == [2, 3]
assert intersection([1, 2, 2, 1], [2, 2]) == [2]
assert intersection([2, 2], [1, 2, 2, 1]) == [2]
Psuedocode for Solution #2¶
# create empty list of common unique values
# create empty set of unique num1 values
# for num1 in nums1:
# code below ensures we only check unique values of nums1 are in nums2...
# if num1 is not in in set:
# add num1 to set
# check if num1 is in nums2...
# for num2 in nums2:
# if num1 is equal to num2:
# append num1 to list of common unique values
# return list of common unique values
Complexity¶
Let n be the length of nums1 and m be the length of nums2.
Space Complexity¶
I create a set that at worst case scenario could contain all values in nums1 and therefore it's an O(n) space complexity.
I create another set that's unique common values between nums1 and nums2 that could contain all values in the smaller of the input lists. I'll consider this O(n) space complexity too.
Lastly, I convert the set of unique common values into a list because that's the needed return data type. That's another O(n).
Total space complexity is O(3n). The 3 is negligent so most would refer to this as O(n).
Time Complexity¶
For each value in nums1, I could check if that value is in nums2. Therefore the space complexity is O(m*n).
Additionally, to convert a Python set to a list is another O(n) operation.
Conclusion¶
Overall, this time and space complexity is smaller than the inital brute force solution in this tutorial. Here's a table that compares the two:
| Solution #1 | ||
|---|---|---|
| Space complexity | O(n) + O(m) | O(n) |
| Time complexity | O(n) + O(m) + O(m*n) | O(m*n) + O(n) |
Code for Solution #2¶
def intersection(nums1, nums2):
common_unique_values_set = set()
nums_in_nums1_checked_set = set()
for num1 in nums1:
if num1 not in nums_in_nums1_checked_set:
nums_in_nums1_checked_set.add(num1)
for num2 in nums2:
if num1 == num2:
common_unique_values_set.add(num1)
common_unique_values_list = list(common_unique_values_set)
return common_unique_values_list
Verify Test Cases for Solution #2¶
assert intersection([1, 2], [4, 5]) == []
assert intersection([1, 3, 3, 4], [3, 0, 5]) == [3]
assert intersection([1, 2, 3, 4], [2, 3]) == [2, 3]
assert intersection([1, 2, 2, 1], [2, 2]) == [2]
assert intersection([2, 2], [1, 2, 2, 1]) == [2]